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 <bits/stdc++.h>
using namespace std;
constexpr int maxN = 2e5+7, biciory = 2;

int n,a[maxN],trie[maxN*biciory][2],cnt[maxN*biciory],c=0,ans;
set<int>same,done;

struct essa{
    int xxor,num,from;
    bool operator <(essa E) const{
        return xxor > E.xxor;
    }
};
priority_queue<essa>pq;

void add(int x, int val){
    int curr = 0;
    for(int i=biciory;i>=0;i--){
        cnt[curr] += val;
        bool bit = ((1 << i) & x);
        if(!trie[curr][bit])
            trie[curr][bit] = ++c;
        curr = trie[curr][bit];
    }
    cnt[curr] += val;
}

int Find(int x){
    int res = 0, curr = 0;
    if(!cnt[curr])
        return -1;
    for(int i=biciory;i>=0;i--){
        bool bit = ((1 << i) & x);
        if(trie[curr][bit] && cnt[trie[curr][bit]]){
            curr = trie[curr][bit];
            if(bit)
                res += (1 << i);
        }
        else{
            curr = trie[curr][!bit];
            if(!bit)
                res += (1 << i);
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    vector<int>A;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        if(same.count(a))
            continue;
        A.push_back(a);
        add(A.back(),1);
    }
    add(A[0], -1);
    int last = A[0];
    done.insert(A[0]);
    for(int i=1;i<(int)A.size();i++){
        int x = Find(last), before;
        pq.push({x^last, x, last});
        while(done.count(pq.top().num)){
            before = pq.top().from;
            pq.pop();
            x = Find(before);
            if(x != -1)
                pq.push({x^before, x, before});
        }
        ans += pq.top().xxor;
        last = pq.top().num;
        done.insert(last);
        add(last, -1);
        before = pq.top().from;
        pq.pop();
        x = Find(before);
        if(x != -1)
            pq.push({x^before, x, before});
    }
    cout<<ans<<"\n";
}
/*

5
1 2 3 4 5

4
1 2 3 4

*/