A survey drone records the elevation at each of n markers along a mountain ridge, in the order it flew over them. A climbing route is any subsequence of markers (they need not be adjacent) whose elevations are read in the recorded order and are strictly increasing. Report the greatest number of markers such a route can contain.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the elevations in recorded order.
Output format
A single integer: the length of the longest strictly increasing subsequence.
Constraints
- 1 <= n <= 100000
- -1000000000 <= elevation <= 1000000000