Description

一个数的序列$b_i$，在$b_1 < b_2 < \ldots < b_S$时，被称为上升序列。给定一个序列$(a_1, a_2, \ldots, a_N)$，可以从中找到一些上升子序列$(a_{i1}, a_{i2}, \ldots, a_{iK})$，其中$1 \leq i_1 < i_2 < \ldots < i_K \leq N$。例如，序列$(1,7,3,5,9,4,8)$的上升子序列包括$(1,7)$和$(3,4,8)$等。这些子序列中最长的长度为4，如子序列$(1,3,5,8)$所示。

你的任务是，针对给定的序列，求出其最长上升子序列的长度。

Input Format

输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

## Output Format

最长上升子序列的长度。

input:

7
1 7 3 5 9 4 8

output:

4