问题描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，请你求出该序列的最长上升子序列（Longest Increasing Subsequence，简称 LIS）的长度。

子序列是指从原序列中删除若干个元素（也可以不删除），保持剩余元素相对顺序不变得到的新序列。

上升子序列是指该子序列满足：

其中：

请你输出最长上升子序列的长度。

输入格式

第一行包含一个整数 $n$，表示序列长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示给定序列。

输出格式

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

样例输入

8
10 9 2 5 3 7 101 18

样例输出

4

说明

该序列的一个最长上升子序列为：

2 3 7 101

长度为 $4$。

其他合法的上升子序列还包括：

2 5 7 18

长度也为 $4$。

可以证明最长上升子序列的长度为 $4$。

评测数据规模

对于所有数据，满足：

$1 \le n \le 5000$

$1 \le a_i \le 5000$