题目描述

给定 $n$ 个数 $a_1,a_2,a_3\cdots a_{n-1},a_n$ ，求这 $n$ 个数的最长上升子序列的长度.

最长上升子序列 就是给你一个序列，请你在其中求出一段不断严格上升的部分，它不一定要连续.

比如： $[2,3,4,7]$ 和 $[2,3,4,6]$ 就是序列 $[2,5,3,4,1,7,6]$ 的两种选取方案。最长的长度是 $4$ .

输入格式

第一行一个整数 $n$ ,

接下来一行 $n$ 个用空格隔开的整数,表示序列 $a$ .

输出格式

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

样例

7
2 5 3 4 1 7 6

4

数据规模与约定

对于 $100\%$数据， $1\le n \le 10^3$ , $0\le a_i\le 10^{6}(1\le i\le n)$ .

注意：此题为全自动对拍题，数据完全随机。