CF340D.Bubble Sort Graph

Iahub recently has learned Bubble Sort, an algorithm that is used to sort a permutation with n elements _a_1, _a_2, ..., a__n in ascending order. He is bored of this so simple algorithm, so he invents his own graph. The graph (let's call it G) initially has n vertices and 0 edges. During Bubble Sort execution, edges appear as described in the following algorithm (pseudocode).

procedure bubbleSortGraph()
build a graph G with n vertices and 0 edges
repeat
swapped = false
for i = 1 to n - 1 inclusive do:
if a[i] > a[i + 1] then
add an undirected edge in G between a[i] and a[i + 1]
swap( a[i], a[i + 1] )
swapped = true
end if
end for
until not swapped
/* repeat the algorithm as long as swapped value is true. */
end procedure

For a graph, an independent set is a set of vertices in a graph, no two of which are adjacent (so there are no edges between vertices of an independent set). A maximum independent set is an independent set which has maximum cardinality. Given the permutation, find the size of the maximum independent set of graph G, if we use such permutation as the premutation a in procedure bubbleSortGraph.

伊阿胡布最近学习了冒泡排序（Bubble Sort）算法，该算法用于将一个包含 $n$ 个元素 $a_1, a_2, \dots, a_n$ 的排列按升序排序。他对这种过于简单的算法感到厌倦，于是发明了自己的图。该图（我们称之为 $G$）初始时包含 $n$ 个顶点、$0$ 条边。在执行冒泡排序的过程中，边会按照以下算法（伪代码）逐步添加：

procedure bubbleSortGraph()
构造一个图 $G$，其包含 $n$ 个顶点、$0$ 条边
repeat
swapped = false
for $i = 1$ 到 $n - 1$（含端点） do:
if $a[i] > a[i + 1]$ then
在图 $G$ 中添加一条连接 $a[i]$ 与 $a[i + 1]$ 的无向边
交换 $a[i]$ 与 $a[i + 1]$
swapped = true
end if
end for
until not swapped
/* 当 swapped 值为 true 时，重复执行该算法。 */
end procedure

对于一个图，独立集（independent set）是指图中的一组顶点，其中任意两个顶点之间均无边相连（即独立集内顶点两两不邻接）。最大独立集（maximum independent set）是所有独立集中基数（顶点数）最大的那个。给定一个排列，请你求出：若将该排列作为上述 bubbleSortGraph 过程中的输入排列 $a$，所生成的图 $G$ 的最大独立集的大小。

The first line of the input contains an integer n (2 ≤ n ≤ 105). The next line contains n distinct integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ n).

输入的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）。下一行包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）。

Output a single integer — the answer to the problem.

输出一个整数——该问题的答案。

Consider the first example. Bubble sort swaps elements 3 and 1. We add edge (1, 3). Permutation is now [1, 3, 2]. Then bubble sort swaps elements 3 and 2. We add edge (2, 3). Permutation is now sorted. We have a graph with 3 vertices and 2 edges (1, 3) and (2, 3). Its maximal independent set is [1, 2].

考虑第一个例子。冒泡排序交换了元素 3 和 1，我们添加一条边 $(1, 3)$。此时排列变为

$$1, 3, 2$$

接着，冒泡排序交换了元素 3 和 2，我们添加一条边 $(2, 3)$。此时排列已排好序。我们得到一个包含 3 个顶点和 2 条边 $(1, 3)$ 与 $(2, 3)$ 的图。该图的最大独立集为

$$[1, 2]$$