Rising Trend

Time limit1sMemory limit128 MB

Summary

For each test case, compute the length of the longest strictly increasing subsequence in a sequence of up to 100000 prices.

Level: Medium4 of 10
Topics: Dynamic programming, Binary search, Array
Solved: No attempts yet

Problem

Jeongin, who enjoys stock investing, wants to study the rising trend of a stock price.

Jeongin wrote down the stock price on each of $n$ days and now wants to find a rising trend in it.

Let the prices over the $n$ days be $p_1, p_2, \ldots, p_n$ . A rising trend is a subsequence $p_{i_1} < p_{i_2} < \cdots < p_{i_k}$ with indices $i_1 < i_2 < \cdots < i_k$ ; that is, a strictly increasing subsequence of the prices.

Given the prices over the $n$ days, write a program that finds the longest rising trend.

Input

The input consists of several test cases; read until end of input. The first line of each test case contains $N$ , the number of days on which the price was observed ( $N \le 100000$ ). The second line contains the observed prices in order from the first day. The prices are separated by one or more spaces, and whitespace may also appear freely at other positions. Each price is a natural number no greater than 100,000.

Output

For each test case, output the length of the longest rising trend among the given prices.

Examples3

Example 1
Input
```
6
5 2 1 4 5 3
3
1 1 1
4
4 3 2 1
```
Expected output
```
3
1
1
```
Example 2
Input
```
7
1 2 3 4 5 6 7
```
Expected output
```
7
```
Example 3
Input
```
5
7 7 7 7 7
```
Expected output
```
1
```