说明

天虎是个烤肉的一把好手。小黑吃一口天虎烤的肉能直接变成星星眼 (✧~✧)。

现在天虎烤了很多烤串，它们被插在地上，每串烤串上的肉块的数量都不一定相同，

天虎想从这些烤串中找出一组烤串，这组烤串要求第 i 支烤串上的肉块的数量都比第 j 支烤串上的肉块小。

天虎想将这组烤串给小黑，但是他一时半会儿也找不到是哪些烤串，所以请你帮他找出这些烤串中符合条件的最长长度。

输入格式

第一行给出烤串的总数 N ( N < = 1000 )

第二行给出每串上的烤肉的数量。

输出格式

输出一行最大长度。

样例

7
1 7 3 5 9 4 8

4

提示

就是求长度为 N 的数组中的最长上升子序列的长度。