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 đơn điệu là 1 dãy A[i_1], A[i_2], ..., A[i_k] thỏa mãn i_1 < i_2 < ... < i_k và A[i_1] < A[i_2] < ... < A[i_k]. Hãy cho biết dãy con tăng đơn điệu 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 <= 1000).
Dòng thứ 2 ghi N số nguyên A[1], A[2], ..., A[N] (1 <= A[i] <= 10000).

Output

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

Example

Input:
5
3 2 4 7 1

Output:
3