CF1828B.Permutation Swap

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 \lt 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$.

给你一个未排序的排列 $p_1, p_2, \ldots, p_n$。为了将该排列排序，你需要选定一个常数 $k$（$k \ge 1$），然后对该排列执行若干次操作。每次操作中，你可以选择两个整数 $i$、$j$（满足 $1 \le j \lt i \le n$ 且 $i - j = k$），然后交换 $p_i$ 和 $p_j$。

你能选择的、使得该排列可被排序的最大 $k$ 值是多少？

排列是指由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的任意顺序的数组。例如，$[2, 3, 1, 5, 4]$ 是一个排列，但 $[1, 2, 2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1, 3, 4]$ 也不是排列（此时 $n = 3$，但数组中出现了 $4$）。

未排序的排列 $p$ 是指至少存在一个位置 $i$ 满足 $p_i \ne i$ 的排列。

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}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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}$。

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.

对于每个测试用例，输出能使给定排列被排序的最大 $k$ 值。

可以证明答案总是存在。

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]$

在第一个测试用例中，你可以选择的最大 $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]$