题目描述

Given a non-negative integer sequence $A = a_1, a_2, \dots, a_n$ of length $n$, define

$$F(A)=\max\limits_{1\leq k<n} ((a_1 \,\&\, a_2 \,\&\, \cdots \,\&\, a_k)+(a_{k+1} \,\&\, a_{k+2} \,\&\, \cdots \,\&\, a_n)) $$

where $\&$ is the bitwise-and operator.

You can perform the swapping operation at most once: choose two indices $i$ and $j$ such that $1\leq i < j\leq n$ and then swap the values of $a_i$ and $a_j$.

Calculate the maximum possible value of $F(A)$ after performing at most one swapping operation.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($2\leq n\leq 10^5$) indicating the length of sequence $A$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($0\leq a_i\leq 10^9$) indicating the given sequence $A$.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^5$.

输出格式

For each test case output one line containing one integer indicating the maximum possible value of $F(A)$ after performing at most one swapping operation.

题目大意

【题目描述】

给定长度为 $n$ 的非负整数序列 $A = a_1, a_2, \dots, a_n$，定义

$$F(A)=\max\limits_{1\leq k<n} ((a_1 \,\&\, a_2 \,\&\, \cdots \,\&\, a_k)+(a_{k+1} \,\&\, a_{k+2} \,\&\, \cdots \,\&\, a_n)) $$

其中 $\&$ 表示按位与操作。

您可以进行至多一次交换操作：选择两个下标 $i$ 和 $j$ 满足 $1\leq i < j\leq n$，交换 $a_i$ 与 $a_j$ 的值。

求经过至多一次交换后，$F(A)$ 的最大值。

【输入格式】

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$2\leq n\leq 10^5$)，表示序列 $A$ 的长度。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0\leq a_i\leq 10^9$)，表示给定的序列 $A$。

保证所有数据 $n$ 之和不超过 $10^5$。

【输出格式】

每组数据输出一行一个整数，表示经过至多一次交换后 $F(A)$ 的最大值。

【样例解释】

对于第一组样例数据，可以交换 $a_4$ 和 $a_6$ 将序列变为 $\{6, 5, 4, 6, 5, 3\}$，然后选择 $k = 5$，就得到了 $F(A) = (6 \,\&\, 5 \,\&\, 4 \,\&\, 6 \,\&\, 5) + (3) = 7$。

对于第二组样例数据，可以交换 $a_2$ 和 $a_4$ 将序列变为 $\{1, 1, 1, 2, 2, 2\}$，然后选择 $k = 3$，就得到了 $F(A) = (1 \,\&\, 1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$。

对于第三组样例数据，不进行交换操作，然后选择 $k = 2$，就得到了 $F(A) = (1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$。

3
6
6 5 4 3 5 6
6
1 2 1 1 2 2
5
1 1 2 2 2

7
3
3

提示

For the first sample test case, we can swap $a_4$ and $a_6$ so the sequence becomes $\{6, 5, 4, 6, 5, 3\}$. We can then choose $k = 5$ so that $F(A) = (6 \,\&\, 5 \,\&\, 4 \,\&\, 6 \,\&\, 5) + (3) = 7$.

For the second sample test case, we can swap $a_2$ and $a_4$ so the sequence becomes $\{1, 1, 1, 2, 2, 2\}$. We can then choose $k = 3$ so that $F(A) = (1 \,\&\, 1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$.

For the third sample test case we do not perform the swapping operation. We can then choose $k = 2$ so that $F(A) = (1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$.