题目描述

有 𝑛𝑛 个不相同的整数组成的数列，记为: 𝑎(1）, 𝑎（2）, … … , 𝑎(𝑛)，例如： 3， 18， 7，14， 10， 12， 23， 41， 16， 24。 上例中挑出： 3， 18， 23， 24就是一个长度为4的上升序列，如果挑出： 3， 7， 10， 12， 16， 24长度为6的上升序列。求出最长的上升序列的长度。

输入格式

第一行一个整数𝑛𝑛(1 <= 𝑛 <= 1000) 第二行为 𝑛 个空格隔开的整数。

输出格式

最长上升子序列的长度。

样例

输入样例

10
3 18 7 14 10 12 23 41 16 24

输出样例

6

数据范围与提示

10%数据，如样例所述； 数据点2中，输入的20个整数严格上升； 数据点3中，输入的20个整数严格下降； 数据点4中，输入的1000个整数相等； 数据点5中， 𝑛 <= 10； 数据点6~10无特殊限制， 1 <= 𝑛 <= 1000。