Longest Increasing Subsequence 3

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

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

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