CF1828B Permutation Swap

给定一个未排序的排列 $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$ 的 $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$。 可以证明答案总是存在。

在第一个测试用例中，你能选择的最大 $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]$ 由 ChatGPT 4.1 翻译