A student's test scores over the term are listed in order. Pick some of them, keeping their original order, so that each picked score is strictly higher than the one before. Print the largest number of scores you can pick.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ score ≤ 10^9
Input and output
- Input
- Line 1: n. Line 2: n integers.
- Output
- One integer.
Examples
Input 1
8
10 9 2 5 3 7 101 18Output
4One longest rising run of picks is 2, 3, 7, 18 (length 4).
Input 2
3
7 7 7Output
1Equal values do not count as rising, so 1.
Show hints
- An O(n²) DP works: len[i] = 1 + the best len[j] with j < i and a[j] < a[i].
- For O(n log n), keep tails[k] = the smallest possible last value of a rising run of length k + 1, and binary-search it.
Show the explanation
The quadratic DP is the classic first answer. The faster method keeps an array tails, where tails[k] is the smallest ending value of any increasing subsequence of length k + 1 seen so far; it is always sorted. For each score, binary-search for the first tail ≥ the score (a lower bound, since increases must be strict) and replace it, or append if none exists. The length of tails is the answer. tails itself is not necessarily a valid subsequence — only its length is meaningful.
Original UniCircle question. Last reviewed 22 Oct 2026.