Description

A sequence of numbers $b_i$ is called increasing when $b_1 < b_2 < ... < b_S$. For a given sequence $(a_1, a_2, ..., a_N)$, we can obtain some increasing subsequences $(a_{i1}, a_{i2}, ..., a_{iK})$, where $1 \leq i_1 < i_2 < ... < i_K \leq N$. Your task is to find the length of the longest increasing subsequence for the given sequence.

Input Format

The first line of input is the length of the sequence, $N$ ($1 \leq N \leq 1000$).
The second line contains $N$ integers of the sequence, where each integer ranges from $0$ to $10000$.

Output Format

The length of the longest increasing subsequence.

7
1 7 3 5 9 4 8

4