← 返回题目列表

Codeforces · 1638/C

C. 反演图

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

给你一个排列 $$$p_1, p_2, \dots, p_n$$$。然后,按以下方式构造无向图:在顶点 $$$i$$$ 和 $$$j$$$ 之间添加一条边,使得 $$$i < j$$$ 当且仅当 $$$p_i > p_j$$$ 时。您的任务是计算该图中连接组件的数量。

当且仅当沿着连接 $$$u$$$ 和 $$$v$$$ 的边至少有一条路径时,两个顶点 $$$u$$$ 和 $$$v$$$ 属于同一连通分量。

排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 排列的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 $$$k$$$ — 连接组件的数量。

示例

输入 #1

6
3
1 2 3
5
2 1 4 3 5
6
6 1 4 2 5 3
1
1
6
3 2 1 6 5 4
5
3 1 5 2 4

输出 #1

3
3
1
1
2
1

注意

每个单独的测试用例如下图所示。彩色方块代表排列的元素。对于一种排列,每种颜色代表一些连接的组件。不同颜色的数量就是答案。