题目描述

给你一个长度为 $n$ 的序列 $a_1\sim a_n$，请你求出该序列中最长上升子序列的长度。
定义一组序列 $b_1\sim b_m$ 是 $a_1\sim a_n$ 的子序列当且仅当 $b$ 可以通过 $a$ 删除若干个元素（也可以不删）后剩下的元素保持相对顺序不变形成。
例如：序列 $a=[1,2,3,4,5]$，序列 $b=[2,4,5]$ 是 $a$ 的子序列。

输入格式

第一行一个整数 $n(1\le n\le 5000)$。
第二行 $n$ 个整数 $a_1\sim a_n(1\le a_i\le 10^9)$。

输出格式

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

输入输出样例 #1

输入 #1

6
3 2 1 4 3 5

输出 #1

3