#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e6+42;
int n;
vector<int> X,Y;
int pointer=0;
int stop;
bool type[nmax];
void push(int node,int val)
{
//cout<<"push "<<node<<" "<<val<<endl;
if(node<stop)
{
int to=-X[node];
if(type[node]==1)to=-Y[node];
type[node]=!type[node];
push(to,val);
return;
}
else
{
if(type[node]==0)X[node]=val;
else Y[node]=val;
type[node]=!type[node];
return;
}
}
/*
void answer(vector<int> c,vector<int> x,vector<int> y)
{
cout<<c.size()<<" "<<x.size()<<" "<<y.size()<<endl;
cout<<"c: ";for(auto k:c)cout<<k<<" ";cout<<endl;
cout<<"x: ";for(auto k:x)cout<<k<<" ";cout<<endl;
cout<<"y: ";for(auto k:y)cout<<k<<" ";cout<<endl;
}
*/
void create_circuit(int M, std::vector<int> A)
{
n=A.size();
vector<int> C={};
for(int j=0;j<=M;j++)
C.push_back(-1);
int k=1;
while((1<<k)<n+1)k++;
stop=(1<<(k-1));
for(int i=0;i<(1<<k);i++)
{
X.push_back(-1);
Y.push_back(-1);
}
for(int i=1;i<(1<<(k-1));i++)
{
X[i]=-(2*i);
Y[i]=-(2*i+1);
}
for(int i=0;i<n;i++)
{
push(1,A[i]);
}
for(int i=(1<<(k-1));i<(1<<k);i++)
{
if(X[i]!=-1&&Y[i]!=-1)continue;
if(X[i]!=-1)
{
swap(X[i],Y[i]);
X[i]=-i;
}
else
{
X[i]=-i;
}
}
X.erase(X.begin(),X.begin()+1);
Y.erase(Y.begin(),Y.begin()+1);
answer(C,X,Y);
}
