1682B.md (2200B)
1 Source: https://codeforces.com/problemset/problem/1682/B 2 3 B. AND Sorting 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$). 22 23 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: 24 25 * Choose two indices $i$ and $j$ $(1 \le i \lt j \le n)$ such that $p_i \& p_j = X$. 26 * Swap $p_i$ and $p_j$. 27 28 Here $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). 29 30 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. 31 32 Input 33 34 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. 35 36 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. 37 38 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. 39 40 It is guaranteed that the sum of $n$ over all cases does not exceed $2 \cdot 10^5$. 41 42 Output 43 44 For each test case output a single integer — the maximum value of $X$ such that $p$ is $X$-sortable. 45 46 Example 47 48 Input 49 50 ``` 51 4 52 53 4 54 55 0 1 3 2 56 57 2 58 59 1 0 60 61 7 62 63 0 1 2 3 5 6 4 64 65 5 66 67 0 3 2 1 4 68 ``` 69 70 Output 71 72 ``` 73 2 74 0 75 4 76 1 77 ``` 78 79 Note 80 81 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$. 82 83 Sorting using $X = 0$: 84 85 * Swap $p_1$ and $p_4$, $p = [2, 1, 3, 0]$. 86 * Swap $p_3$ and $p_4$, $p = [2, 1, 0, 3]$. 87 * Swap $p_1$ and $p_3$, $p = [0, 1, 2, 3]$. 88 89 Sorting using $X = 2$: 90 91 * Swap $p_3$ and $p_4$, $p = [0, 1, 2, 3]$. 92 93 In the second test case, we must swap $p_1$ and $p_2$ which is possible only with $X = 0$.