Xor-MST

题目描述

给定一个包含 $n$ 个顶点的完全无向图。每个顶点 $i$ 上有一个数值 $a_i$，连接顶点 $i$ 和顶点 $j$ 的边的权值为 $a_i \oplus a_j$（$\oplus$ 表示按位异或）。

请计算该图的最小生成树的权值。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 200000$）—— 图中顶点的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < 2^{30}$）—— 每个顶点上的数值。

输出格式

输出一个整数 —— 该图的最小生成树的权值。

样例输入1

5
1 2 3 4 5

样例输出1

8

样例输入2

4
1 2 3 4

样例输出2

8