A shipping yard has
Find the maximum number of containers that can be selected to form such a strictly increasing stack.
The first line contains a single integer KaTeX can only parse string typed expression — the number of containers. If KaTeX can only parse string typed expression, there are no containers.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the size of each container, in yard order.
Print a single integer — the maximum number of containers that can be stacked in strictly increasing order of size, keeping their original relative order.
Input
8
10 9 2 5 3 7 101 184Selecting containers of size KaTeX can only parse string typed expression (in that relative order from the yard) forms a valid strictly increasing stack of 4 containers, which is optimal.
Example 2:
Input
5
5 4 3 2 11The sizes are strictly decreasing, so at most a single container can be selected (any two containers would violate the strictly-increasing requirement).
Example 3:
Input
6
5 5 5 5 5 51All containers are the same size, and the stack must be strictly increasing (equal sizes don't count), so only one container can be selected.