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

Cho một hoán vị $a_1,a_2,\dots ,a_N$ của các số từ $1$ đến $N$.

Ta xây dựng một đồ thị vô hướng $G$ gồm $N$ đỉnh, được đánh số từ $1$ đến $N$ (đỉnh mang giá trị của phần tử, không phải vị trí), ban đầu không có cạnh nào. Các cạnh được thêm vào trong quá trình chạy thuật toán sắp xếp nổi bọt trên dãy $a$:

repeat
    swapped = false
    for i = 1 to N - 1:
        if 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
until 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 đó được nối với nhau bằng 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 của 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ụ