Longest Ordered Subsequence
time limit per test 2 second memory limit per test 256 megabytes
A numeric sequence of ai is ordered if a1 < a2 < … < aN. Let the subsequence of the given numeric sequence (a1, a2, …, aN) be any sequence (ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

## Input

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 10000 each, separated by spaces. 1 <= N <= 1000

## Output

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

## 题解

## TLE code:(不包含输入类)
O(nlogn)做法: 多一个记录数组，遍历第一遍数组时，对每个数字进行判断，如果它比记录数组中最后一位还大，那就加入到记录数组中，否则用二分查找在记录数组中找到比它大的最小的下标，把那个下标的值更新为它。最后记录数组的长度就是LIS的长度
## AC code:(不包含输入类)