您有一组 $$$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$$$。
对于 [0, m - 1]$$$ 中的每个 $$$k,在执行第一个 $$$k$$$ 查询后计算塔组的难度。
输入
输入的第一行包含两个整数 $$$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$$$ 查询之前)。
输出
打印 $$$m$$$ 整数。第 $$$k$$$ 个整数($$$0$$$ 索引)应等于执行第一个 $$$k$$$ 查询后塔组的难度。
示例
输入 #1
7 4 1 2 3 3 1 4 3 3 1 2 3 2 4
输出 #1
5 4 2 0
注意
示例中的塔是:
- 查询之前:$$$[[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]$$$。