AND Sorting

题意翻译

有 $T$ 次询问。每次询问给你一个 $0 \sim n - 1$ 的排列 $p_1, p_2, \ldots, p_n$，保证此排列初始时没有排好序。你可以初始指定一个数 $X$，然后你每次可以交换两个数 $p_i, p_j$，此时必须满足 $p_i \mathbin{\&} p_j = X$，问要使得原排列有序的 $X$ 的最大值。

题目描述

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>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](https://en.wikipedia.org/wiki/Bitwise_operation#AND). 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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

4
4
0 1 3 2
2
1 0
7
0 1 2 3 5 6 4
5
0 3 2 1 4

输出样例 #1

2
0
4
1

说明

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

题目大意：
这个题目是关于一个称为“AND排序”的排序问题。给定一个从0到n-1的整数排列（每个数字恰好出现一次），最初这个排列是无序的。要确定一个非负整数X，通过以下操作将排列变为有序：

- 选择两个索引i和j（1≤i - 交换pi和pj的位置。

这里的&表示按位与操作。需要找到最大的X值，使得排列可以通过上述操作变为有序。可以证明，总是存在某个X值使得排列可以通过上述操作变为有序。

输入输出数据格式：
输入包括多个测试用例。第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。接下来是每个测试用例的描述。

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

每个测试用例的第二行包含n个整数p1, p2, ..., pn（0≤pi≤n-1，所有pi都是不同的），表示排列的元素。保证排列是无序的。

所有测试用例的n之和不超过2×10^5。

对于每个测试用例，输出一个整数，即最大的X值，使得排列可以通过上述操作变为有序。

输入输出样例：
输入样例 #1
```
4
4
0 1 3 2
2
1 0
7
0 1 2 3 5 6 4
5
0 3 2 1 4
```
输出样例 #1
```
2
0
4
1
```
说明：
在第一个测试用例中，只有X=0和X=2时排列可以通过操作变为有序，其中最大的值是2。

使用X=0进行排序的过程：
- 交换p1和p4，p = [2, 1, 3, 0]。
- 交换p3和p4，p = [2, 1, 0, 3]。
- 交换p1和p3，p = [0, 1, 2, 3]。

使用X=2进行排序的过程：
- 交换p3和p4，p = [0, 1, 2, 3]。

在第二个测试用例中，我们必须交换p1和p2，这只能通过X=0实现。题目大意： 这个题目是关于一个称为“AND排序”的排序问题。给定一个从0到n-1的整数排列（每个数字恰好出现一次），最初这个排列是无序的。要确定一个非负整数X，通过以下操作将排列变为有序： - 选择两个索引i和j（1≤i