题目描述

给定一个长度为$n$的序列：$A_1,A_2......A_n$，求序列$A$的最长不下降子序列的长度。

输入

第一行输入一个整数$n$，表示序列$A$的长度。 第二行输入$n$个数，分别是$A_1,A_2......A_n$。

输出

一个整数，即序列$A$的最长不下降子序列的长度。

样例数据

11
1 3 6 3 4 7 5 7 6 7 8

8

数据范围

$0<n\le10^6$

$-2^{31}\le A_i<2^{31}$