Matryoshka là một loại búp bê rất nổi tiếng của Nga. Với việc có ~1~ con búp bê nằm trong ~1~ con búp bê khác, và lại có ~1~ con búp bê khác nữa nằm trong con búp bê, ... LamTer hôm nay vừa được bố mẹ mua cho ~n~ con búp bê, ~n~ con búp bê này được xếp thành ~1~ đường thẳng, con thứ ~i~ có kích thước là ~a_i~.

LamTer quyết định sẽ chồng một số con búp bê vào nhau sao cho số lượng búp bê được chồng trong ~1~ con nào đó là lớn nhất. Biết rằng con búp bê thứ ~i~ có thể chồng vào được con búp bê thứ ~j~ nếu như ~i < j~ và ~a_i < a_j~.

Hãy giúp LamTer tìm số lượng búp bê chồng vào nhau lớn nhất nhé.

Input

Gồm ~2~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số búp bê.
• Dòng thứ hai chứa ~n~ số nguyên dương thể hiện dãy ~a~.

Output

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

Constraint

• ~n \leq 1000~
• ~a_i \leq 10^9~

Subtask

• Subtask 1 (25%): ~n \leq 20~.
• Subtask 2 (25%): ~a_i \leq 3~.
• Subtask 3 (50%): không có ràng buộc gì thêm.

Sample Input

5
1 4 3 2 5

Sample Output

3

Note

• Chọn dãy búp bê lồng nhau gồm các búp bê có kích thước ~1, 3~ và ~5~.