Longest Increasing Subsequence 3

Time limit3sMemory limit512 MB

Summary

Given a sequence of up to 10^6 integers, find the length of the longest strictly increasing subsequence.

Level: Medium5 of 10
Topics: Dynamic programming, Binary search
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 you get by picking some elements of $A$ and keeping their original order. An increasing subsequence is one whose values grow from left to right, so the same value may not appear twice in it.

For example, if $A = \{10, 20, 10, 30, 20, 50\}$ , then 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 10^6$ )

The second line contains the integers $A_1, A_2, \dots, A_N$ of the sequence $A$ , separated by spaces. ( $-10^9 \le A_i \le 10^9$ )

Output

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

Examples2

Example 1
Input
```
6
10 20 10 30 20 50
```
Expected output
```
4
```
Example 2
Input
```
6
5 5 5 5 5 5
```
Expected output
```
1
```