#P888G. Xor-MST
-
ID: 4077
Type: RemoteJudge
2000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Xor-MST
No submission language available for this problem.
Description
You are given a complete undirected graph with n vertices. A number ai is assigned to each vertex, and the weight of an edge between vertices i and j is equal to ai xor aj.
Calculate the weight of the minimum spanning tree in this graph.
The first line contains n (1 ≤ n ≤ 200000) — the number of vertices in the graph.
The second line contains n integers a1, a2, ..., an (0 ≤ ai < 230) — the numbers assigned to the vertices.
Print one number — the weight of the minimum spanning tree in the graph.
Input
The first line contains n (1 ≤ n ≤ 200000) — the number of vertices in the graph.
The second line contains n integers a1, a2, ..., an (0 ≤ ai < 230) — the numbers assigned to the vertices.
Output
Print one number — the weight of the minimum spanning tree in the graph.
Samples
5
1 2 3 4 5
8
4
1 2 3 4
8