Longest Increasing Subsequence 2

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$.

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$)

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