For a given sequence $A=a_0,a_1,…,a_{n−1}$, find the length of the longest increasing subsequnece (LIS) in $A$.

An increasing subsequence of $A$ is defined by a subsequence $a_{i_0},a_{i_1},…,a_{i_k}$ where $0≤i_0<i_1<…<i_k<n$ and $a_{i_0}<a_{i_1}<…<a_{i_k}$.

$n$

$a_0$

$a_1$

$:$

$a_{n−1}$

In the first line, an integer $n$ is given. 

In the next $n$ lines, elements of $A$ are given.