给出一个长度为 $n$ 的整数序列，请你输出它的最长不上升子序列的长度。

输入格式

第一行为一个整数 $n$ 表示序列长度

第二行为 $n$ 个正整数，表示该整数序列（每个数均小于 $10^7$ ）

输出格式

一个整数ans，表示最长不上升子序列的长度。

样例

样例输入

7
12 5 3 7 5 4 3

样例输出

5

（样例解释：12，7，5，4，3是它的一个最长的不上升子序列，长度为5)

来源

动态规划练习

数据范围与提示

• 对于30%的数据，$n\le 50$
• 对于60%的数据，$n\le 500$
• 对于100%的数据，$n\le 5000$
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$32768\mathrm{KB}$