Igor Perić

B. AND Sorting

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

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, pi>pi+1 for at least one 1≤i≤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≤i<j≤n) such that pi&pj=X.
• Swap pi and pj.

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

The input consists of multiple test cases. The first line contains a single integer t (1≤t≤104)  — the number of test cases. Description of test cases follows.

The first line of each test case contains a single integer n (2≤n≤2⋅105)  — the length of the permutation.

The second line of each test case contains n integers p1,p2,…,pn (0≤pi≤n−1, all pi 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⋅105.

Output

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

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

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 p1 and p4, p=[2,1,3,0].
• Swap p3 and p4, p=[2,1,0,3].
• Swap p1 and p3, p=[0,1,2,3].

Sorting using X=2:

• Swap p3 and p4, p=[0,1,2,3].

In the second test case, we must swap p1 and p2 which is possible only with X=0.

Solution

The first observation is we must swap only the numbers which are not in their spot, so the first thing we’ll do is sort the array so we can check for each number if it needs to be moved at all.

Since swapping operation doesn’t change the positioning of the elements not participating in the swap, we know the order of the swaps doesn’t matter for the final solution. The only this that matters are the pairs of numbers participating in the swaps. Since this chain of swaps must use all of the unsorted numbers, we know the X we’re searching for must allow swapping any of the pairs in this chain. Effectively, this means applying the AND operation to all of the numbers which are out of position will give us our X.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<unsigned long long> a(n);
        for (int i=0;i<n;i++) cin >> a[i];

      	// make a sorted copy of A
        vector<unsigned long long> b(a);
        sort(b.begin(), b.end());

        long long sol = -1;
        for (int i=0;i<n;i++) {
          	// needs to be swapped?
            if (a[i] != b[i]) {
              	// handle the first number
                if (sol == -1) sol = a[i]; 
                else sol &= a[i];
            }
        }
        cout << sol << endl;
    }

    return 0;
}