310401: CF1828B. Permutation Swap

B. Permutation Swaptime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an unsorted permutation $p_1, p_2, \ldots, p_n$. To sort the permutation, you choose a constant $k$ ($k \ge 1$) and do some operations on the permutation. In one operation, you can choose two integers $i$, $j$ ($1 \le j < i \le n$) such that $i - j = k$, then swap $p_i$ and $p_j$.

What is the maximum value of $k$ that you can choose to sort the given permutation?

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2, 3, 1, 5, 4]$ is a permutation, but $[1, 2, 2]$ is not a permutation ($2$ appears twice in the array) and $[1, 3, 4]$ is also not a permutation ($n = 3$ but there is $4$ in the array).

An unsorted permutation $p$ is a permutation such that there is at least one position $i$ that satisfies $p_i \ne i$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^{5}$) — the length of the permutation $p$.

The second line of each test case contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the permutation $p$. It is guaranteed that the given numbers form a permutation of length $n$ and the given permutation is unsorted.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

Output

For each test case, output the maximum value of $k$ that you can choose to sort the given permutation.

We can show that an answer always exists.

ExampleInput

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

Output

1
2
3
4
3
2
3

Note

In the first test case, the maximum value of $k$ you can choose is $1$. The operations used to sort the permutation are:

• Swap $p_2$ and $p_1$ ($2 - 1 = 1$) $\rightarrow$ $p = [1, 3, 2]$
• Swap $p_2$ and $p_3$ ($3 - 2 = 1$) $\rightarrow$ $p = [1, 2, 3]$

In the second test case, the maximum value of $k$ you can choose is $2$. The operations used to sort the permutation are:

• Swap $p_3$ and $p_1$ ($3 - 1 = 2$) $\rightarrow$ $p = [1, 4, 3, 2]$
• Swap $p_4$ and $p_2$ ($4 - 2 = 2$) $\rightarrow$ $p = [1, 2, 3, 4]$

题目大意：
给定一个未排序的排列 \( 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 \) 的最大值，以便对给定的排列进行排序。

输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例的数量 \( 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 \) 的最大值，以便对给定的排列进行排序。

示例：
输入：
```
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
2
3
4
3
2
3
```

注意：
在第一个测试用例中，你可以选择的 \( k \) 的最大值是 \( 1 \)。用于排序排列的操作是：
- 交换 \( p_2 \) 和 \( p_1 \)（\( 2 - 1 = 1 \)）→ \( p = [1, 3, 2] \)
- 交换 \( p_2 \) 和 \( p_3 \)（\( 3 - 2 = 1 \)）→ \( p = [1, 2, 3] \)

在第二个测试用例中，你可以选择的 \( k \) 的最大值是 \( 2 \)。用于排序排列的操作是：
- 交换 \( p_3 \) 和 \( p_1 \)（\( 3 - 1 = 2 \)）→ \( p = [1, 4, 3, 2] \)
- 交换 \( p_4 \) 和 \( p_2 \)（\( 4 - 2 = 2 \)）→ \( p = [1, 2, 3, 4] \)题目大意： 给定一个未排序的排列 \( 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 \) 的最大值，以便对给定的排列进行排序。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例的数量 \( 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 \) 的最大值，以便对给定的排列进行排序。 示例： 输入： ``` 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 2 3 4 3 2 3 ``` 注意： 在第一个测试用例中，你可以选择的 \( k \) 的最大值是 \( 1 \)。用于排序排列的操作是： - 交换 \( p_2 \) 和 \( p_1 \)（\( 2 - 1 = 1 \)）→ \( p = [1, 3, 2] \) - 交换 \( p_2 \) 和 \( p_3 \)（\( 3 - 2 = 1 \)）→ \( p = [1, 2, 3] \) 在第二个测试用例中，你可以选择的 \( k \) 的最大值是 \( 2 \)。用于排序排列的操作是： - 交换 \( p_3 \) 和 \( p_1 \)（\( 3 - 1 = 2 \)）→ \( p = [1, 4, 3, 2] \) - 交换 \( p_4 \) 和 \( p_2 \)（\( 4 - 2 = 2 \)）→ \( p = [1, 2, 3, 4] \)