← 返回题单

题单练习位运算

← 上一题下一题 →

A6469 | $按位与排序$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Welcome24ever 有一排卡片，上面写着从 $0$ 到 $n-1$ 每个数各一次（也就是一个排列）。现在这些卡片还没排好从小到大。 他发明了一条“交换规则”：只要选中两张卡片 $p_i$ 和 $p_j$（$ij$），并且它们做按位与（AND）得到的结果刚好等于某个数 $X$，他就可以把这两张卡片交换位置。 如果通过若干次这样的交换，能把卡片排成 $[0,1,2,\ldots,n-1]$，我们就说这个排列是 “$X$-可排序” 的。 你的任务是：在所有让这个排列变得可排序的 $X$ 中，找出最大的那个 $X$。

输入格式

有多组测试数据。 第一行一个整数 $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

C++ 编辑器

输入

输出