有一个长为 $n$ 的序列 $a_0, a_1,...,a_{n - 1}$。

求出这个序列的最长上升子序列的长度。

上升子序列指的是对于任意的 $i < j$ 都满足 $a_i < a_j$ 的子序列。

输入

• 第一行为一个整数 $n$
• 第二行有 $n$ 个整数表示序列 $a$
• $1 \leq n \leq 1000$
• $1 \leq a_i \leq 10^6$

输出

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