Đồ thị sắp xếp nổi bọt

Cho một hoán vị $a_1,a_2,\dots ,a_n$ của $1,2,\dots ,n$.

Ta xây dựng một đồ thị vô hướng $G$ gồm $n$ đỉnh (đánh số $1$ đến $n$) và ban đầu không có cạnh nào, bằng cách chạy thuật toán sắp xếp nổi bọt trên dãy $a$:

lặp lại
    swapped = false
    với i = 1 đến n - 1:
        nếu a[i] > a[i + 1]:
            thêm cạnh vô hướng giữa hai đỉnh a[i] và a[i + 1]
            đổi chỗ a[i] và a[i + 1]
            swapped = true
cho đến khi swapped = false

Một tập độc lập của $G$ là một tập các đỉnh mà không có hai đỉnh nào trong tập được nối bởi một cạnh. Hãy tìm kích thước của tập độc lập lớn nhất của $G$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên đôi một phân biệt $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Một số nguyên duy nhất: kích thước tập độc lập lớn nhất của $G$.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le a_i\le n$, các $a_i$ đôi một phân biệt.

Ví dụ