Longest Ordered Subsequence#2649
A numeric sequence a_i is called ordered if a_1 \leq a_2 \leq \dots \leq a_N. A subsequence of the given numeric sequence (a_1, a_2, \dots, a_N) is any sequence (a_{i_1}, a_{i_2}, \dots, a_{i_K}), where 1 \leq i_1 < i_2 < \dots < i_K \leq N.
For example, the sequence (1, 7, 3, 5, 9, 4, 8) contains ordered subsequences such as , (3, 4, 8), and so on. All longest ordered subsequences of this sequence have length , for example (1, 3, 5, 8).
Given a numeric sequence, find the length of its longest ordered subsequence.
The first line contains the length of the sequence (1 \leq N \leq 10^5). The second line contains the elements of the sequence — integers, each in the range from to 10^6.
Output a single integer — the length of the longest ordered subsequence of the given sequence.
Example 1