CF1380E.Merging Towers

You have a set of $n$ discs, the $i$-th disc has radius $i$. Initially, these discs are split among $m$ towers: each tower contains at least one disc, and the discs in each tower are sorted in descending order of their radii from bottom to top.

You would like to assemble one tower containing all of those discs. To do so, you may choose two different towers $i$ and $j$ (each containing at least one disc), take several (possibly all) top discs from the tower $i$ and put them on top of the tower $j$ in the same order, as long as the top disc of tower $j$ is bigger than each of the discs you move. You may perform this operation any number of times.

For example, if you have two towers containing discs $[6, 4, 2, 1]$ and $[8, 7, 5, 3]$ (in order from bottom to top), there are only two possible operations:

• move disc $1$ from the first tower to the second tower, so the towers are $[6, 4, 2]$ and $[8, 7, 5, 3, 1]$;
• move discs $[2, 1]$ from the first tower to the second tower, so the towers are $[6, 4]$ and $[8, 7, 5, 3, 2, 1]$.

Let the difficulty of some set of towers be the minimum number of operations required to assemble one tower containing all of the discs. For example, the difficulty of the set of towers $[[3, 1], [2]]$ is $2$: you may move the disc $1$ to the second tower, and then move both discs from the second tower to the first tower.

You are given $m - 1$ queries. Each query is denoted by two numbers $a_i$ and $b_i$, and means "merge the towers $a_i$ and $b_i$" (that is, take all discs from these two towers and assemble a new tower containing all of them in descending order of their radii from top to bottom). The resulting tower gets index $a_i$.

For each $k \in [0, m - 1]$, calculate the difficulty of the set of towers after the first $k$ queries are performed.

你有一组 $n$ 个圆盘，其中第 $i$ 个圆盘的半径为 $i$。初始时，这些圆盘被分配在 $m$ 座塔中：每座塔至少包含一个圆盘，且每座塔内的圆盘按半径从下到上严格递减排列。

你希望将所有圆盘组装成一座塔。为此，你可以执行如下操作：任选两座不同的塔 $i$ 和 $j$（每座塔均至少含一个圆盘），从塔 $i$ 的顶部取出若干（可能全部）圆盘，并以相同顺序叠放在塔 $j$ 的顶部；该操作合法当且仅当塔 $j$ 当前顶部圆盘的半径严格大于你所移动的每一个圆盘的半径。你可以执行该操作任意多次。

例如，若你有两座塔，分别包含圆盘 $[6, 4, 2, 1]$ 和 $[8, 7, 5, 3]$（均按从下到上顺序列出），则仅有两种合法操作：

• 将第一座塔顶部的圆盘 $1$ 移至第二座塔，得到塔 $[6, 4, 2]$ 和 $[8, 7, 5, 3, 1]$；
• 将第一座塔顶部的圆盘 $[2, 1]$ 移至第二座塔，得到塔 $[6, 4]$ 和 $[8, 7, 5, 3, 2, 1]$。

定义某组塔的难度为：将其合并为一座包含全部圆盘的塔所需的最少操作次数。例如，塔集合 $[[3, 1], [2]]$ 的难度为 $2$：可先将圆盘 $1$ 移至第二座塔，再将第二座塔中的两个圆盘整体移至第一座塔。

现给出 $m - 1$ 个查询。每个查询由两个数 $a_i$ 和 $b_i$ 表示，含义为“合并塔 $a_i$ 和塔 $b_i$”（即取出这两座塔的所有圆盘，按半径从大到小自上而下重新组成一座新塔）。新塔的编号为 $a_i$。

对每个 $k \in [0, m - 1]$，计算执行前 $k$ 个查询后所得塔集合的难度。

The first line of the input contains two integers $n$ and $m$ ($2 \le m \le n \le 2 \cdot 10^5$) — the number of discs and the number of towers, respectively.

The second line contains $n$ integers $t_1$, $t_2$, ..., $t_n$ ($1 \le t_i \le m$), where $t_i$ is the index of the tower disc $i$ belongs to. Each value from $1$ to $m$ appears in this sequence at least once.

Then $m - 1$ lines follow, denoting the queries. Each query is represented by two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le m$, $a_i \ne b_i$), meaning that, during the $i$-th query, the towers with indices $a_i$ and $b_i$ are merged ($a_i$ and $b_i$ are chosen in such a way that these towers exist before the $i$-th query).

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le m \le n \le 2 \cdot 10^5$），分别表示圆盘的数量和塔的数量。

第二行包含 $n$ 个整数 $t_1$, $t_2$, ..., $t_n$（$1 \le t_i \le m$），其中 $t_i$ 表示第 $i$ 个圆盘所属的塔的编号。该序列中，从 $1$ 到 $m$ 的每个值至少出现一次。

随后是 $m - 1$ 行，表示查询操作。每个查询由两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le m$，且 $a_i \ne b_i$）组成，表示在第 $i$ 次查询中，将编号为 $a_i$ 和 $b_i$ 的塔合并（$a_i$ 和 $b_i$ 的选取保证了这二者在第 $i$ 次查询前均存在）。

Print $m$ integers. The $k$-th integer ($0$-indexed) should be equal to the difficulty of the set of towers after the first $k$ queries are performed.

输出 $m$ 个整数。其中第 $k$ 个整数（从 $0$ 开始编号）应等于执行前 $k$ 个查询后塔集合的难度值。

The towers in the example are:

• before the queries: $[[5, 1], [2], [7, 4, 3], [6]]$;
• after the first query: $[[2], [7, 5, 4, 3, 1], [6]]$;
• after the second query: $[[7, 5, 4, 3, 2, 1], [6]]$;
• after the third query, there is only one tower: $[7, 6, 5, 4, 3, 2, 1]$.

示例中的塔为：

• 查询前：$[[5, 1], [2], [7, 4, 3], [6]]$；
• 第一次查询后：$[[2], [7, 5, 4, 3, 1], [6]]$；
• 第二次查询后：$[[7, 5, 4, 3, 2, 1], [6]]$；
• 第三次查询后，仅剩一座塔：$[7, 6, 5, 4, 3, 2, 1]$。