Longest Increasing Subsequence

Problem statement

A progress log contains numerical scores in time order. An analyst wants the longest improving trend after optionally omitting readings, while preserving the order of every reading that remains. Your task Find the length of the longest strictly increasing subsequence. Important details A subsequence may skip positions and need not be contiguous. Equal values do not extend a strictly increasing trend. Return the length rather than one chosen subsequence. Aim for O(n log n) time using ordered candidate tails. Worked example From [4, 1, 3, 2, 5], choose [1, 3, 5] or [1, 2, 5]. Both have length 3, and no longer strictly increasing subsequence exists.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the maximum subsequence length.

Constraints

1 <= n <= 2500; -10000 <= values <= 10000.

Sample input

5
4 1 3 2 5

Sample output

3