T3--最小生成链(1s/512M)

题目描述

定义一张图的生成链是原图的一棵生成树，且这棵树退化成一条链。我们称一条生成链是原图的最小生成链，当且仅当它当中边权最大的边是原图的所有生成链中最小的。

现有一个 $n$ 个点的完全图，点编号为 $1$ 到 $n$。另给出一个长度为 $n$ 的序列 $a_i$，完全图中第 $i$ 个点与第 $j$ 个点间的边的边权为 $a_i\oplus a_j$，其中 $\oplus$ 表示异或运算。

请你找出该完全图的最小生成链。但由于答案可能很多，你只需要输出这条最小生成链中边权最大的边的边权即可。

输入格式

第一行输入一个正整数 $n$，表示这个完全图的点数。第二行输入 $n$ 个非负整数 $a_i$，表示这个序列。

输出格式

输出一行一个非负整数 $w$，表示这条生成链中边权最大值。

样例

见 down/msc 目录下的样例文件。

数据范围

对于 $20\%$ 的数据，$n\leq 8$；

对于 $40\%$ 的数据，$n\leq 17$；

对于 $60\%$ 的数据，$n\leq 10^3$；

对于另外 $20\%$ 的数据，$a_i\in [0,1]$；

对于 $100\%$ 的数据，$2\leq n\leq 2\times 10^5$，$0\leq a_i<2^{60}$。