3689. [CF1682B]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$。

如果经过若干次操作后，$p$ 可以变成升序排列，那么称 $p$ 是 “$X$ 可排”的。

求 $X$ 的最大值。

【输入格式】

第一行一个整数 $T$ 表示数据组数。

每组数据第一行有一个整数 $n$，表示排列的长度。

接下来一行，$n$ 个整数 $p_1,p_2,\ldots ,p_n$（$0 \le p_i \lt n$，所有 $p_i$ 两两不同），表示排列 $p$ 中的元素。

保证所有排列 $p$ 均未排好序，所有数据的 $n$ 的和不超过 $2\times 10^5$。

【输出格式】

一个最大的整数 $X$，使得 $p$ 是 “$X$ 可排” 的。

【样例输入】

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

【样例输出】

2
0
4
1

【样例说明】

在第一组数据中，$X$ 可以为 $0$ 或 $2$。

当 $X=0$ 时，我们可以交换 $(p_1,p_4),(p_3,p_4),(p_1,p_3)$。

当 $X=2$ 时，我们可以交换 $(p_3,p_4)$。

在第二组数据中，我们必须交换 $(p_1,p_2)$，因此 $X$ 只能为 $0$。

【数据规模与约定】

$\sum {n} \le 2 \times 10^5$,$\forall i \in [1,n],p_i \in [0,n-1]$

【来源】

Codeforces Round #793 Div.2 Problem B