题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，请你求出它的最长严格上升子序列的长度。子序列不要求连续，只要保持原来的先后顺序即可。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，依次为 $a_1\sim a_n$，用空格隔开。

输出格式

一行一个整数，表示最长严格上升子序列的长度。

输入输出样例 #1

输入 #1

8
1 7 3 5 9 4 8 2

输出 #1

4

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^6$，$|a_i|\le 10^9$。