题目描述

给你一个$n$个元素的正整数序列$a[\ ]$，找出这个数组的最长上升子序列。

注：最长上升子序列（Longest Increasing Subsequence，简称LIS）是指在一个序列中找到一个最长的子序列，使得子序列中的元素按照升序排列。

例如，对于序列 [10, 22, 9, 33, 21, 50, 41, 60, 80]，其中的最长上升子序列是 [10, 22, 33, 50, 60, 80]，长度为 6。

输入格式

第一行一个整数$n$，表示序列长度。 第二行$n$个整数$a_i$，表示序列元素。

输出格式

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

样例

5
1 3 2 5 4

3

数据范围

对于$30\%$的数据， $n \leq 20$。

对于$60\%$的数据，$n \leq 2000$。

对于$100\%$的数据，$n \leq 2000000$。