A6469. 按位与排序
编程题
普及-
知识点
题目描述
Welcome24ever 有一排卡片，上面写着从 $0$ 到 $n-1$ 每个数各一次（也就是一个**排列**）。现在这些卡片还没排好从小到大。
他发明了一条“交换规则”：只要选中两张卡片 $p_i$ 和 $p_j$（$i<j$），并且它们做**按位与**（AND）得到的结果**刚好等于**某个数 $X$，他就可以把这两张卡片交换位置。
如果通过若干次这样的交换，能把卡片排成 $[0,1,2,\ldots,n-1]$，我们就说这个排列是 **“$X$-可排序”** 的。
你的任务是：在所有让这个排列变得可排序的 $X$ 中，找出**最大的**那个 $X$。
他发明了一条“交换规则”：只要选中两张卡片 $p_i$ 和 $p_j$（$i<j$），并且它们做**按位与**（AND）得到的结果**刚好等于**某个数 $X$，他就可以把这两张卡片交换位置。
如果通过若干次这样的交换，能把卡片排成 $[0,1,2,\ldots,n-1]$，我们就说这个排列是 **“$X$-可排序”** 的。
你的任务是：在所有让这个排列变得可排序的 $X$ 中，找出**最大的**那个 $X$。
输入格式
有多组测试数据。
第一行一个整数 $t$，表示测试组数。
接下来每组：
- 第一行一个整数 $n$；
- 第二行是一个长度为 $n$ 的排列 $p_1,p_2,\ldots,p_n$（每个数都在 $[0,n-1]$ 且互不相同）。保证这个排列一开始不是升序。
第一行一个整数 $t$，表示测试组数。
接下来每组：
- 第一行一个整数 $n$；
- 第二行是一个长度为 $n$ 的排列 $p_1,p_2,\ldots,p_n$（每个数都在 $[0,n-1]$ 且互不相同）。保证这个排列一开始不是升序。
输出格式
对每组数据，输出一个整数：让该排列变为升序时，可能的**最大** $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
说明/提示
## 数据范围
- $1 \le t \le 10^4$
- $2 \le n \le 2\cdot 10^5$
- $0 \le p_i \le n-1$ 且两两不同
- 所有测试中 $n$ 的总和 $\le 2\cdot 10^5$
## 解释
- 第 1 组里，用 $X=2$ 时，只交换一对就能排好序；$X$ 还能取 $0$，但题目要“最大”的 $X$，所以答案是 $2$。
- 第 2 组里，只能直接交换 $1$ 和 $0$，这需要 $X=0$，所以答案是 $0$。
- $1 \le t \le 10^4$
- $2 \le n \le 2\cdot 10^5$
- $0 \le p_i \le n-1$ 且两两不同
- 所有测试中 $n$ 的总和 $\le 2\cdot 10^5$
## 解释
- 第 1 组里，用 $X=2$ 时，只交换一对就能排好序；$X$ 还能取 $0$，但题目要“最大”的 $X$，所以答案是 $2$。
- 第 2 组里，只能直接交换 $1$ 和 $0$，这需要 $X=0$，所以答案是 $0$。