Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N].

Biết rằng dãy con tăng là 1 dãy A[i1],... A[ik] thỏa mãn i1 < i2 < ... < ik và A[i1 ] < A[i2 ] < .. < A[ik ].

Hãy cho biết dãy con tăng dài nhất của dãy này có bao nhiêu phần tử?

Input

• Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 10^5).

• Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10^9).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Ví dụ

Input

10
6 2 4 5 9 10 7 8 9 3

Output

6

Giới hạn:

• Subtask 1 (50%): N ≤ 10^4
• Subtask 2 (50%): N ≤ 10^5