Iahub 最近学习了冒泡排序,这是一种用于对 n 个元素 a1, a2, ..., an 的排列进行升序排序的算法。他厌倦了这种如此简单的算法,所以他发明了自己的图表。该图(我们称之为 G)最初有 n 个顶点和 0 条边。在冒泡排序执行期间,边将按以下算法(伪代码)中的描述出现。
对于图,独立集是图中的一组顶点,其中没有两个顶点是相邻的(因此独立集的顶点之间没有边)。最大独立集是具有最大基数的独立集。给定排列,如果我们使用这样的排列作为过程 bubbleSortGraph 中的预排列 a,求图 G 的最大独立集的大小。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 105)。下一行包含 n 个不同的整数 a1, a2, ..., an (1 ≤ ai ≤ n)。
输出
输出一个整数——问题的答案。
示例
输入 #1
3 3 1 2
输出 #1
2
注意
考虑第一个例子。冒泡排序交换元素 3 和 1。我们添加边 (1, 3)。排列现在为 [1, 3, 2]。然后冒泡排序交换元素 3 和 2。我们添加边 (2, 3)。现在排列已排序。我们有一个具有 3 个顶点和 2 个边 (1, 3) 和 (2, 3) 的图。其最大独立集为[1, 2]。