题目描述

给定一个长度为 $n$ 的数组 $a_1,a_2,…,a_n$，问其中的最长上升子序列的长度。也就是说，我们要找到最大的 $m$ 以及数组 $p_1 , p_2 , … , p_m$，满足 $1≤p_1<p_2<⋯<p_m≤n$ 并且 $a_{p_1}<a_{p_2}<⋯<a_{p_m}$。

输入格式

第一行一个数字 $n$。

接下来一行 $n$ 个整数 $a_1,a_2,…,a_n$。

输出格式

一个数，表示答案。

Samples

6
3 7 4 2 6 8

4

数据规模

对于所有数据，保证 $1≤n≤1000,1≤a_i≤10^9$。