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\le 1000$
• $a_i\le {10}^9$

Subtask

• Subtask 1 (25%): $n\le 20$.
• Subtask 2 (25%): $a_i\le 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$.