中位数的最大值

题目描述

给你一个长度为 $2N$ 的序列:$A = (A_1, A_2, \ldots, A_{2N})$。

通过对序列 $A$ 的元素进行重新排列,求序列 $(A_1 \oplus A_2, A_3 \oplus A_4, \ldots, A_{2N-1} \oplus A_{2N})$ 的中位数所能取得的最大值。

这里,$\oplus$ 表示按位异或。

什么是按位异或?非负整数 $A$ 和 $B$ 的按位异或,记作 $A \oplus B$,定义如下:

在 $A \oplus B$ 的二进制表示中,第 $2^k$ 位($k \ge 0$)的数字为 $1$,当且仅当 $A$ 和 $B$ 的二进制表示中第 $2^k$ 位的数字恰有一个为 $1$,否则为 $0$。

例如,$3 \oplus 5 = 6$(二进制表示:$011 \oplus 101 = 110$)。

另外,对于长度为 $L$ 的序列 $B$,$B$ 的中位数是将 $B$ 按升序排序得到的序列 $B'$ 中第 $\lfloor \frac{L}{2} \rfloor + 1$ 个位置的值。

输入格式

输入按以下格式从标准输入给出:

N
A_1 A_2 … A_{2N}

输出格式

输出答案。

样例

4
4 0 0 11 2 7 9 5

14

通过将 $A$ 重排为 $(5, 0, 9, 7, 11, 4, 0, 2)$,得到 $(A_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8) = (5, 14, 15, 2)$,该序列的中位数为 $14$。

不可能通过重排 $A$ 使 $(A_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8)$ 的中位数达到 $15$ 或更大,因此输出 $14$。

1
998244353 1000000007

1755654

5
1 2 4 8 16 32 64 128 256 512

192

数据范围

• $1 \le N \le 10^5$
• $0 \le A_i \lt 2^{30}$
• 所有输入值均为整数。