AND Sorting
Contest: Codeforces Round 793 (Div. 2)
Difficulty rating: 1100
Tags: bitmasks, constructive algorithms, sortings

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.

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.

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

Example input:
4
4
0 1 3 2
2
1 0
7
0 1 2 3 5 6 4
5
0 3 2 1 4

Example output:
2
0
4
1

Editorial:
We always have to swap elements which are not in their correct positions. Hence an upper bound of answer would be the bitwise AND of elements which are not in their correct positions. Let that value be $$$X$$$. It turns out that the given permutation is $$$X$$$-sortable.
Proof:
First, notice that $$$X$$$ would always be present inside $$$p$$$. Let $$$pos_x$$$ be the position of $$$X$$$ in $$$p$$$. Let's say at some point we want to swap two values $$$p_i$$$ and $$$p_j$$$. Notice that $$$p_i$$$ and $$$p_j$$$ would always be supermask of $$$X$$$ i.e. $$$p_i \& X = X $$$ and $$$p_j \& X = X$$$.
• Swap values at indices $$$i$$$ and $$$pos_x$$$.
• Swap values at indices $$$i$$$ and $$$j$$$.
• Swap values at indices $$$j$$$ and $$$pos_x$$$.
In every swap bitwise AND of values at two indices is $$$X$$$. Hence effectively we swap the values at indices $$$i$$$ and $$$j$$$.