Mingyun's Scheme

Interview

Time limit1sMemory limit256 MB

Summary

Given N cards in order, compute the length of the longest strictly increasing subsequence.

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

Problem

Mingyun enjoys teasing Junmin. Today he prepares $N$ cards, each with one integer written on it, and shows them to Junmin in a fixed order. Junmin picks as many cards as he likes, keeping the order in which they were shown, and hands that sequence back to Mingyun. If the sequence Junmin hands back is not strictly increasing, Mingyun calls him a fool. Strictly increasing means every value is smaller than the value right after it. When the cards shown are $4, 9, 10, 9$ , picking $4, 9$ is safe, while $4, 10, 9$ or $9, 9$ gets Junmin teased.

Junmin never slipped up, so Mingyun added one more condition. The sequence Junmin hands back must be strictly increasing and must also have as many elements as possible. When the cards are $8, 9, 1, 2, 10$ , picking $8, 9, 10$ or $1, 2, 10$ is safe, while $8, 9$ or $1, 2$ gets him teased.

Junmin decided to first work out how many elements such a sequence can have at most. For $8, 9, 1, 2, 10$ that number is $3$ . Write a program that computes it for him.

Input

The first line contains the number of cards $N$ ( $1 \le N \le 1000$ ) that Mingyun shows.

The second line contains the $N$ integers written on the cards, in the order they are shown, separated by spaces. Each integer is between $1$ and $100{,}000{,}000$ .

Output

Print on the first line the maximum number of elements in a sequence Junmin can hand back.

Examples7

Example 1
Input
```
5
8 9 1 2 10
```
Expected output
```
3
```
Example 2
Input
```
8
5 4 3 2 1 6 7 8
```
Expected output
```
4
```
Example 3
Input
```
1
100000000
```
Expected output
```
1
```
Example 4
Input
```
5
7 7 7 7 7
```
Expected output
```
1
```
Example 5
Input
```
6
6 5 4 3 2 1
```
Expected output
```
1
```
Example 6
Input
```
6
1 2 3 4 5 6
```
Expected output
```
6
```
Example 7
Input
```
10
1 3 2 3 4 2 5 1 6 4
```
Expected output
```
6
```