You are given a sequence of integers. A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

Find the length of the longest subsequence whose values are strictly increasing.

Input

The first line contains an integer ~n~, the length of the sequence.

The second line contains ~n~ integers: ~a_1, a_2, \ldots, a_n~.

Output

Print one integer: the length of the longest strictly increasing subsequence.

Constraints

• ~1 \le n \le 5000~
• ~-10^9 \le a_i \le 10^9~

Example 1

Input

8
10 9 2 5 3 7 101 18

Output

4

Explanation

One longest increasing subsequence is ~2, 3, 7, 101~.

Example 2

Input

5
5 4 3 2 1

Output

1

Example 3

Input

6
2 2 2 2 2 2

Output

1