Subsequence

Given a sequence, find the length of the largest strictly increasing subsequence.

Input

First line contains the length $n(1\le n\le 1000)$ of the sequence. The second line contains the sequence itself. All numbers are integers not exceeding $10^4$ by absolute value.

Output

Print the maximum length of strictly increasing subsequence.

Examples