← 返回题目列表

Codeforces · 340/D

D. 冒泡排序图

中文机器翻译题面 查看原题

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]。