Cho một dãy gồm ~n~ số nguyên. Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con.

Input

Dòng đầu tiên gồm số nguyên ~n~ ~(1 \leq n \leq 10^3)~.

Dòng thứ hai gồm ~n~ số, số thứ ~i~ mô tả số nguyên ~a_i~ ~(1 \leq a_i \leq 10^9)~.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán.

Example

Input

6
1 2 5 4 6 2

Output

4

Giải thích

Dãy cần tìm là ~a_1~ ~a_2~ ~a_4~ ~a_5~.