题目描述

给定长度为$n$的整数数列，求最长上升子序列的长度。

输入格式

第一行包含整数$n$。

第二行包含$n$个整数，之间用空格隔开。

输出格式

输出一个整数。

样例

样例 1 输入

6
1 8 2 6 3 9

样例 1 输出

4

说明与提示

1
1

1

2
1 2

2

说明/提示

数据范围

对于30%的数据，$1 ≤ n ≤ 20$。

对于100%的数据，$1 ≤ n ≤ 2000$。