AT_wtf22_day2_e.Adjacent Xor Game

给定 $N$ 个非负整数 $A_1,A_2,\cdots,A_N$。对于每个 $k=1,2,\cdots,N$，请解决以下问题。

Alice 和 Bob 进行如下游戏：

• Alice 从 $A_1,A_2,\cdots,A_N$ 中选择 $k$ 个数。记选出的数为 $x_1,x_2,\cdots,x_k$（顺序不限）。

• Bob 构造一个长度为 $2k$ 的非负整数序列 $y=(y_1,y_2,\cdots,y_{2k})$。其中，$y$ 需要满足以下条件：

  • $0\leq y_1\leq y_2\leq \cdots\leq y_{2k}$
  • 定义 $z_i=y_{2i-1}\oplus y_{2i}$。此时，$\{z_1,z_2,\cdots,z_k\}$ 作为多重集与 $\{x_1,x_2,\cdots,x_k\}$ 完全一致。

其中，$\oplus$ 表示按位异或（XOR）运算。

本次游戏的得分为 $y_{2k}$ 的值。Bob 会选择方案使得得分最小化。在此基础上，Alice 会选择方案使得得分最大化。此时，最终的得分是多少？

按位异或（XOR）运算定义如下：对于非负整数 $A,B$，$A\oplus B$ 的二进制表示中，每一位 $2^k$（$k\geq 0$）的数值等于 $A,B$ 的二进制表示在该位上仅有一个为 $1$ 时为 $1$，否则为 $0$。

例如，$3\oplus 5=6$（二进制为 $011\oplus 101=110$）。
一般地，$k$ 个非负整数 $p_1,p_2,p_3,\dots,p_k$ 的按位异或为 $(\dots((p_1\oplus p_2)\oplus p_3)\oplus\dots\oplus p_k)$，并且可以证明其结果与 $p_1,p_2,\dots,p_k$ 的顺序无关。

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

请输出答案。

限制条件

• $1\leq N\leq 250000$
• $1\leq A_i\leq 10^9$
• 输入的所有值均为整数。

样例解释 1

考虑 $k=1$ 的情况。

• Alice 选择 $x_1=1$ 时：Bob 可以构造 $y=(0,1)$，得分为 $1$。
• Alice 选择 $x_1=2$ 时：Bob 可以构造 $y=(0,2)$，得分为 $2$。
• Alice 选择 $x_1=3$ 时：Bob 可以构造 $y=(1,2)$，得分为 $2$。
  因此，Alice 可以选择 $x_1=2$ 或 $x_1=3$，得分为 $2$。

考虑 $k=2$ 的情况。
Alice 选择 $(x_1,x_2)=(2,3)$，Bob 可以构造 $y=(1,2,4,6)$，得分为 $6$。
这是一种双方最优行动的例子，答案为 $6$。

考虑 $k=3$ 的情况。
Alice 选择 $(x_1,x_2,x_3)=(1,2,3)$，Bob 可以构造 $y=(0,1,1,2,4,6)$，得分为 $6$。
这是一种双方最优行动的例子，答案为 $6$。

由 ChatGPT 4.1 翻译