说明

一个数的序列 $bi$，当 $b1 < b2 < \dots < bS$的时候，我们称这个序列是上升的。

对于给定的一个序列 $(a1, a2, ..., aN)$，我们可以得到一些上升的子序列 $(ai1, ai2, ..., aiK)$，这里 $1 <= i1 < i2 < ... < iK <= N4$。

比如，对于序列 $(1, 7, 3, 5, 9, 4, 8)$，有它的一些上升子序列，如 $(1, 7), (3, 4, 8)$ 等等。

这些子序列中最长的长度是 $4$ ，比如子序列 $(1, 3, 5, 8)$.

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入格式

输出格式

样例

6
1 6 2 4 4 7

4