Longest Increasing Subsequence

Statement

You are given an array of n integers. A subsequence keeps the original order but may skip elements. Find the length of the longest subsequence whose values are strictly increasing.

Input

The first line has n. The second line has n integers.

Output

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

Constraints

1 <= n <= 100000
|a_i| <= 10^9

Example 1

8
10 9 2 5 3 7 101 18

4

For example 2, 3, 7, 101.

Example 2

5
5 4 3 2 1

1

No two elements are in increasing order, so the best is a single element.