该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

序列染色

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

你需要给序列中的每个元素染上一种颜色。对于任意两个位置 $i,j$，如果满足 $i<j$ 且 $a_i$ 与 $a_j$ 被染成了相同的颜色，那么必须有：

也就是说，在每一种颜色对应的子序列中，元素必须按照原序列中的顺序严格递增。

请你求出，在满足条件的前提下，最少需要使用多少种颜色。

输入格式

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

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

数据范围

对于所有测试数据，满足：

输出格式

输出一个整数，表示最少需要使用的颜色数量。

输入输出样例 #1

输入 #1

5
2 1 4 5 3

输出 #1

2