#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pb push_back
#define sz(s) (int)s.size()
using namespace std;
const int MAX=2e5+10;
int cnt;
int t[4*MAX];
bool state[4*MAX];
int get(int v,int tl,int tr){
if(tl==tr)return tl;
int tm=(tl+tr)/2;
state[v]^=1;
if(state[v])return get(2*v,tl,tm);
else return get(2*v+1,tm+1,tr);
}
int x[MAX],y[MAX];
void build(int v,int tl,int tr,vector<int> &a){
if(tl==tr){
if(a[tl]==-1){
t[v]=MAX;
}
else t[v]=a[tl];
return;
}
int tm=(tl+tr)/2;
build(2*v,tl,tm,a);
build(2*v+1,tm+1,tr,a);
if(t[2*v]==MAX&&t[2*v+1]==MAX){
t[v]=MAX;
return;
}
t[v]=--cnt;
// cout<<t[v]<<" "<<tl<<" "<<tr<<"\n";
if(t[2*v]!=MAX){
x[-t[v]]=t[2*v];
}
else{
x[-t[v]]=MAX;
}
if(t[2*v+1]!=MAX){
y[-t[v]]=t[2*v+1];
}
else{
y[-t[v]]=MAX;
}
}
void create_circuit(int M, vector<int> A){
A.pb(0);
int n=sz(A);
int cur=1;
while(cur<sz(A))cur*=2;
vector<int> f(cur+1,-1);
vector<int> ord;
for(int i=0;i<cur;i++){
int pos=get(1,1,cur);
if(pos>=cur-n+1){
ord.pb(pos);
}
// cout<<pos<<" ";
}
// cout<<'\n';
for(int i=0;i<n;i++){
f[ord[i]]=A[i];
}
build(1,1,cur,f);
vector<int> a;
for(int i=0;i<=M;i++)a.pb(t[1]);
vector<int> b,c;
for(int i=1;i<=-cnt;i++){
if(x[i]==MAX)b.pb(t[1]);
else b.pb(x[i]);
if(y[i]==MAX)c.pb(t[1]);
else c.pb(y[i]);
// cout<<-i<<" "<<b[i-1]<<"\n"<<-i<<" "<<c[i-1]<<'\n';
}
// cout<<-cnt<<"\n";
// for(int f:b)cout<<f<<" ";
// cout<<"\n";
// for(int f:c)cout<<f<<" ";
// cout<<"\n";
answer(a,b,c);
}
