Cho dãy số nguyên ~A~ gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~. Một dãy chỉ số ~1 \le i_1 < i_2 < \dots < i_k \le n~ mà ~a_{i_1} < a_{i_2} < \dots < a_{i_k}~, khi đó ~a_{i_1} < a_{i_2} < \dots < a_{i_k}~ được gọi là một dãy con tăng của ~A~. Hãy tìm độ dài dãy con tăng dài nhất của ~A~.

Input

• Dòng đầu ghi số nguyên dương ~n~ ~(n \le 1000)~.
• Dòng hai ghi dãy số nguyên ~A~ ~(|A_i| \le 10^9)~.

Output

• Một số nguyên là độ dài dãy con tăng đơn điệu dài nhất.

Sample Input 1

6
1 2 5 4 6 2

Sample Output 1

4

Sample Input 2

10
1 2 3 4 9 10 5 6 7 8

Sample Output 2

8