← 返回题目列表

Codeforces · 1372/C

C. 奥姆卡和棒球

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

帕特里克喜欢打棒球,但有时他会花很多时间打本垒打,以至于他的头脑开始变得模糊! Patrick 确信他在 $$$n$$$ 会话中的得分遵循身份排列(即,在第一场比赛中他获得 $$$1$$$ 分,在第二场比赛中他获得 $$$2$$$ 分,依此类推)。然而,当他查看自己的记录时,却发现所有的数字都搞混了!

定义一个特殊的交换如下:选择分数的任何子数组并排列元素,使得子数组中的任何元素都不会到达与交换之前相同的位置。例如,对 $$$[1,2,3]$$$ 执行特殊交换可以产生 $$$[3,1,2]$$$,但不能产生 $$$[3,2,1]$$$,因为 $$$2$$$ 处于相同位置。

给定 $$$n$$$ 整数的排列,请帮助帕特里克找到使排列排序所需的特殊交换的最小数量!可以证明,在给定的约束下,这个数字不会超过$$$10^{18}$$$。

数组 $$$a$$$ 是数组 $$$b$$$ 的子数组,如果 $$$a$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$b$$$ 获得。

输入

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

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2},...,a_{n}$$$ ($$$1 \leq a_{i} \leq n$$$) — 初始排列。

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

输出

对于每个测试用例,输出一个整数:对排列进行排序所需的特殊交换的最小数量。

示例

输入 #1

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

输出 #1

0
2

注意

在第一个排列中,它已经排序,因此不需要交换。

可以证明,您至少需要 $$$2$$$ 交换来对第二个排列进行排序。

$$$[3, 2, 4, 5, 1, 6, 7]$$$

在范围 ($$$1, 5$$$) 上执行特殊交换

$$$[4, 1, 2, 3, 5, 6, 7]$$$

在范围 ($$$1, 4$$$) 上执行特殊交换

$$$[1, 2, 3, 4, 5, 6, 7]$$$