Description

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: 10 9 2 5 3 7 101 18

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

Format

Input

第一行，一个整数n，表示数据个数

第二行，n个整数，以空格分隔

Output

输出最大上升子序列长度

Samples

9
2 7 1 5 6 4 3 8 9

5

Limitation

1s, 1024KiB for each test case.