12 1 s 128 MB

A numeric sequence of *a _{i}* is ordered if

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 1,000,000 each, separated by spaces. 1 <= N <= 100,000

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

## Sample Input | ## Sample Output |
---|---|

7 1 7 3 5 9 4 8 | 4 |

O( N lg N ) algorithm is needed