Cho dãy A gồm n số nguyên a1, a2, ..., an khác nhau đôi một.

Yêu cầu: Chia dãy A thành ít nhất các dãy con (có thể không liên tiếp) sao cho:

• Mỗi phần tử của dãy A thuộc một và chỉ một dãy con.
• Mỗi dãy con có thể có một phần tử hoặc nếu nhiều hơn một thì khi giữ nguyên trật tự như ở dãy ban đầu sẽ cho ta một dãy số tăng dần.

• Nếu hai số ai, aj bất kì (1 ≤ i < j ≤ n) thuộc cùng một dãy con thì mọi số ak (k=1..n) mà ai < ak < aj cũng thuộc dãy con đó.

  Dữ liệu: Vào từ tệp văn bản CAU2.INP gồm:

• Dòng đầu chứa số nguyên dương n (n ≤ 10^5);

• Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an (ai ≤ 109 với mọi i = 1..n).

  Kết quả: Ghi ra tệp văn bản CAU2.OUT một số nguyên duy nhất là số dãy con ít nhất tìm được.

Ví dụ:

CAU2.INP
    5
    2 4 1 5 3
CAU2.OUT    
    3
Mô tả
    Các dãy con lần lượt là: 
    Dãy 1: 1
    Dãy 2: 4, 5
    Dãy 3: 2, 3

Ràng buộc:

• Có 40% số điểm có n ≤ 103 và ai ≤ n với mọi i = 1..n;
• Có 40% số điểm tiếp theo có n ≤ 10^5 và ai ≤ n với mọi i = 1..n;
• Có 20% số điểm còn lại không có ràng buộc gì thêm.