Longest Increasing Subsequence

For a given sequence A = {a₀, a₁, ... , a_n-1}, find the length of the longest increasing subsequnece (LIS) in A.

An increasing subsequence of A is defined by a subsequence {a_i0, a_i1, ... , a_ik} where 0 ≤ i₀ < i₁ < ... < i_k < n and a_i0 < a_i1 < ... < a_ik.

Input

n
a0
a1
:
an-1

In the first line, an integer n is given. In the next n lines, elements of A are given.

Output

The length of the longest increasing subsequence of A.

Constraints

• 1 ≤ n ≤ 100000
• 0 ≤ a_i ≤ 10⁹

Sample Input 1

5
5
1
3
2
4

Sample Output 1

3

Sample Input 2

3
1
1
1

Sample Output 2

1

---