说明

设有由n个不相同的整数组成的数列，记为: $a_1,a_2,…,a_n$且$\forall i \not =j,a_i\not=a_j$。例如$3,18,7,14,10,12,23,41,16,24$。若$\exist i_1<i_2<…<i_e，a_{i_1}<a_{i_2}<…<a_{i_e}$则称为长度为e的不下降子序列。如上例中$3,18,23,24$就是一个长度为4的不下降子序列，同时也有$3,7,10,12,16,24$长度为6的不下降子序列。程序要求，当原数列给出之后，求出最长的不下降子序列。

输入格式

第一行为n，表示n个数$（10 \le n \le 10000 ）$
第二行n个整数，数值之间用一个空格分隔$（1 \le a_i \le n）$

输出格式

最长不下降子序列的长度

样例

3
1 2 3

3