You are given a complete undirected graph with *n* vertices. A number *a*<sub class="lower-index">*i*</sub> is assigned to each vertex, and the weight of an edge between vertices *i* and *j* is equal to *a*<sub class="lower-index">*i*</sub> *xor* *a*<sub class="lower-index">*j*</sub>.

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 *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> &lt; 2<sup class="upper-index">30</sup>) — the numbers assigned to the vertices.
none
5
1 2 3 4 5
8
4
1 2 3 4
8
1
1
0
#include<iostream>
#include<vector>
#include<map>
#include <algorithm>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
int L[maxn * 40],R[maxn * 40];
int ch[maxn * 40][2],tot;
int n,root;
int a[maxn];
#define ls ch[now][0]
#define rs ch[now][1]
void Insert(int &now,int x,int dep) {
    if(!now) now = ++tot;
    L[now] = min(L[now],x);R[now] = max(R[now],x);
    if(dep < 0) return;
    int bit = x >> dep & 1;
    Insert(ch[now][bit],x,dep - 1);
}

ll query(int now,int val,int dep) {
    if(dep < 0) return 0;
    int bit = (val >> dep) & 1;
    if(ch[now][bit]) return query(ch[now][bit],now,dep - 1);
    return query(ch[now][bit ^ 1],now,dep - 1) + (1 << dep);
}

ll dfs(int now,int dep) {
    if(dep < 0) return 0;
    if(R[ch[now][0]] && R[ch[now][1]]) {
        ll mi = INF;
        for(int i = L[ch[now][0]];i <= R[ch[now][0]];i++) {
            mi = min(mi,query(ch[now][1],a[i],dep - 1));
        }
        return dfs(ch[now][0],dep - 1) + mi + dfs(ch[now][1],dep - 1) + (1 << dep);
    }
    if(R[ch[now][0]]) return dfs(ch[now][0],dep - 1);
    if(R[ch[now][1]]) return dfs(ch[now][1],dep - 1);
    return 0;
}

int main() {
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
    }
    sort(a + 1,a + 1 + n);
    memset(L,0x3f,sizeof(L));
    for(int i = 1;i <= n;i++) Insert(root, i, 30);
    printf("%lld\n",dfs(root,30));
    return 0;
}

