Longest Increasing Subsequence 2

Interview

Time limit1sMemory limit512 MB

Summary

Given up to 1,000,000 numbers, compute the length of the longest strictly increasing subsequence.

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

Problem

Given a sequence $A$ , write a program that computes the length of its longest increasing subsequence.

A subsequence of $A$ is what remains after deleting zero or more elements and keeping the rest in their original order. A subsequence is increasing when every element is strictly smaller than the element right after it. Two elements with the same value cannot sit next to each other in one increasing subsequence.

For example, if $A = \{10, 20, 10, 30, 20, 50\}$ , the longest increasing subsequence is $\{10, 20, 30, 50\}$ and its length is $4$ .

Input

The first line contains the size $N$ of the sequence $A$ . ( $1 \le N \le 1\,000\,000$ )

The second line contains $A_1, A_2, \dots, A_N$ , separated by single spaces. ( $1 \le A_i \le 1\,000\,000$ )

Output

Print the length of the longest increasing subsequence of $A$ on the first line.

Examples5

Example 1
Input
```
6
10 20 10 30 20 50
```
Expected output
```
4
```
Example 2
Input
```
1
1000000
```
Expected output
```
1
```
Example 3
Input
```
5
5 4 3 2 1
```
Expected output
```
1
```
Example 4
Input
```
6
7 7 7 7 7 7
```
Expected output
```
1
```
Example 5
Input
```
8
1 2 3 4 5 6 7 8
```
Expected output
```
8
```