Given an array of n integers, return the length of its longest strictly increasing subsequence.
A subsequence is obtained by deleting zero or more elements without changing the order of the remaining elements. "Strictly increasing" means each chosen element is greater than the one before it. You must return only the length, which is uniquely determined even when several subsequences achieve it.
Input format
Line 1: a single integer n (the array length).
Line 2: n space-separated integers. This line is absent when n = 0.
Output format
A single line containing one integer: the length of the longest strictly increasing subsequence. For an empty array the answer is 0.
Constraints
- 0 ≤ n ≤ 100000
- -10^9 ≤ a[i] ≤ 10^9
Example
For a = [10, 9, 2, 5, 3, 7, 101, 18] one longest strictly increasing subsequence is [2, 3, 7, 18] (or [2, 3, 7, 101]), so the length is 4.