#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
std::vector<int> X, Y;
int add_switch(){
X.push_back(0);
Y.push_back(0);
return (int)X.size()-1;
}
void set_child(int x, int l, int r){
X[x] = l;
Y[x] = r;
}
int get_reverse(int x, int log){
int ret = 0;
for(int i = log; i >= 0; i--)
if(x&(1<<i))
ret += (1<<(log-i));
return ret;
}
int build(vector<int> &v, int l, int r){
if(l+1 == r)
return v[l];
int m = (l+r)/2, x = add_switch();
set_child(x, build(v, l, m), build(v, m, r));
return -x-1;
}
int add(int x, vector<int> v){
int n = (int)v.size();
while(n != (n&(-n))) n += (n&(-n));
//cout<<n<<" asd"<<endl;
reverse(v.begin(), v.end());
v.resize(n, -(int)X.size()-1);
reverse(v.begin(), v.end());
vector<int> v2(n);
int log = 31 - __builtin_clz(n);
//cout<<"added "<<log<<endl;
for(int i = 0; i < n; i++){
//cout<<i<<" "<<get_reverse(i, log-1)<<endl;
v2[get_reverse(i, log-1)] = v[i];
}
return build(v2, 0, n);
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
map<int, vector<int>> kov;
kov[0].push_back(A[0]);
for(int i = 0; i < N; i++){
if(i < N-1){
kov[A[i]].push_back(A[i+1]);
} else
kov[A[i]].push_back(0);
}
std::vector<int> C(M + 1, 0);
for(auto d : kov){
//cout<<d.second.size()<<" "<<d.first<<"\n";
if(d.second.size() == 1){
C[d.first] = d.second[0];
} else
C[d.first] = add(d.first, d.second);
}
//for(int i = 0; i < M+1; i++)
//cout<<i<<" -> "<<C[i]<<"\n";
answer(C, X, Y);
}
