CF1682B.AND Sorting

You are given a permutation $p$ of integers from $0$ to $n-1$ (each of them occurs exactly once). Initially, the permutation is not sorted (that is, $p_i \gt p_{i+1}$ for at least one $1 \le i \le n - 1$).

The permutation is called $X$-sortable for some non-negative integer $X$ if it is possible to sort the permutation by performing the operation below some finite number of times:

• Choose two indices $i$ and $j$ $(1 \le i \lt j \le n)$ such that $p_i \& p_j = X$.
• Swap $p_i$ and $p_j$.

Here $\&$ denotes the bitwise AND operation.

Find the maximum value of $X$ such that $p$ is $X$-sortable. It can be shown that there always exists some value of $X$ such that $p$ is $X$-sortable.

给你一个由 $0$ 到 $n-1$ 的整数构成的排列 $p$（每个整数恰好出现一次）。初始时，该排列未排序（即至少存在一个下标 $1 \le i \le n - 1$，使得 $p_i \gt p_{i+1}$）。

对于某个非负整数 $X$，若可通过有限次执行以下操作将该排列排序，则称该排列是 $X$-可排序的：

• 选择两个下标 $i$ 和 $j$（满足 $1 \le i \lt j \le n$），使得 $p_i \& p_j = X$；
• 交换 $p_i$ 和 $p_j$。

其中 $\&$ 表示按位与运算。

请找出最大的 $X$ 值，使得 $p$ 是 $X$-可排序的。可以证明：总存在某个 $X$ 值使得 $p$ 是 $X$-可排序的。

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. Description of test cases follows.

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

The second line of each test case contains $n$ integers $p_1, p_2, ..., p_n$ ($0 \le p_i \le n-1$, all $p_i$ are distinct) — the elements of $p$. It is guaranteed that $p$ is not sorted.

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

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示排列的长度。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$（$0 \le p_i \le n-1$，且所有 $p_i$ 互不相同），即排列 $p$ 的元素。保证 $p$ 不是升序排列的。

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

For each test case output a single integer — the maximum value of $X$ such that $p$ is $X$-sortable.

对于每个测试用例，输出一个整数——使得 $p$ 是 $X$-可排序的最大 $X$ 值。

In the first test case, the only $X$ for which the permutation is $X$-sortable are $X = 0$ and $X = 2$, maximum of which is $2$.

Sorting using $X = 0$:

• Swap $p_1$ and $p_4$, $p = [2, 1, 3, 0]$.
• Swap $p_3$ and $p_4$, $p = [2, 1, 0, 3]$.
• Swap $p_1$ and $p_3$, $p = [0, 1, 2, 3]$.

Sorting using $X = 2$:

• Swap $p_3$ and $p_4$, $p = [0, 1, 2, 3]$.

In the second test case, we must swap $p_1$ and $p_2$ which is possible only with $X = 0$.

在第一个测试用例中，使得该排列为 $X$-可排序的唯一 $X$ 值是 $X = 0$ 和 $X = 2$，其中最大值为 $2$。

使用 $X = 0$ 进行排序：

• 交换 $p_1$ 与 $p_4$，得到 $p = [2, 1, 3, 0]$。
• 交换 $p_3$ 与 $p_4$，得到 $p = [2, 1, 0, 3]$。
• 交换 $p_1$ 与 $p_3$，得到 $p = [0, 1, 2, 3]$。

使用 $X = 2$ 进行排序：

• 交换 $p_3$ 与 $p_4$，得到 $p = [0, 1, 2, 3]$。

在第二个测试用例中，我们必须交换 $p_1$ 与 $p_2$，而这仅当 $X = 0$ 时才可行。