← 返回题目列表

Codeforces · 1828/B

B. 排列交换

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

给你一个未排序的排列 $$$p_1, p_2, \ldots, p_n$$$。要对排列进行排序,您可以选择一个常量 $$$k$$$ ($$$k \ge 1$$$) 并对排列进行一些操作。在一次操作中,您可以选择两个整数 $$$i$$$、$$$j$$$ ($$$1 \le j < i \le n$$$) 使得 $$$i - j = k$$$,然后交换 $$$p_i$$$ 和 $$$p_j$$$。

您可以选择对给定排列进行排序的 $$$k$$$ 的最大值是多少?

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

未排序排列 $$$p$$$ 是一种排列,使得至少有一个位置 $$$i$$$ 满足 $$$p_i \ne i$$$。

输入

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

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

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$。保证给定的数字形成长度为 $$$n$$$ 的排列,并且给定的排列是未排序的。

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

输出

对于每个测试用例,输出您可以选择对给定排列进行排序的 $$$k$$$ 的最大值。

我们可以证明答案总是存在的。

示例

输入 #1

7
3
3 1 2
4
3 4 1 2
7
4 2 6 7 5 3 1
9
1 6 7 4 9 2 3 8 5
6
1 5 3 4 2 6
10
3 10 5 2 9 6 7 8 1 4
11
1 11 6 4 8 3 7 5 9 10 2

输出 #1

1
2
3
4
3
2
3

注意

在第一个测试用例中,您可以选择的 $$$k$$$ 的最大值是 $$$1$$$。用于对排列进行排序的操作是:

- 交换 $$$p_2$$$ 和 $$$p_1$$$ ($$$2 - 1 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 3, 2]$$$
- 交换 $$$p_2$$$ 和 $$$p_3$$$ ($$$3 - 2 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3]$$$

在第二个测试用例中,您可以选择的 $$$k$$$ 的最大值是 $$$2$$$。用于对排列进行排序的操作是:

- 交换 $$$p_3$$$ 和 $$$p_1$$$ ($$$3 - 1 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 4, 3, 2]$$$
- 交换 $$$p_4$$$ 和 $$$p_2$$$ ($$$4 - 2 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3, 4]$$$