#include "doll.h"
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> og;
int s=1;
vector<int> x,y;
int recur(int l,int r)
{
if(og[l]==-1 and og[r]==-1)
return -1;
if(l==r)
{
return og[l];
}
int mid=(l+r)/2;
int p=x.size();
x.push_back(-1);
y.push_back(-1);
int lc,rc;
lc=recur(l,mid),rc=recur(mid+1,r);
x[p]=lc;
y[p]=rc;
return -p-1;
}
vector<int> perm(vector<int> a)
{
if(a.size()==1)
{
return a;
}
int n=a.size();
vector<int> cur[2];
for(int i=0;i<n;i++)
{
cur[i%2].push_back(a[i]);
}
vector<int> fp=perm(cur[0]);
vector<int> sp=perm(cur[1]);
fp.insert(fp.end(),sp.begin(),sp.end());
return fp;
}
void create_circuit(int m, std::vector<int> a) {
x.clear();
y.clear();
og=a;
int on=a.size();
int n=a.size();
auto tmp=a;
tmp.push_back(0);
s=1;
while((1<<__lg(n+1))!=(n+1))
{
a.push_back(-1);
n++;
}
a.push_back(0);
n++;
vector<int> lo;
for(int x=0;x<n;x++)lo.push_back(x);
lo=perm(lo);
vector<pair<int,int>> st;
int kp=on;
// while((kp<<1)<=on)kp<<=1;
int gg=on;
on=kp;
// cout<<gg<<' '<<on<<' '<<kp<<endl;
for(int i=0;i<on;i++)
{
st.push_back({lo[i],i});
}
sort(begin(st),end(st));
// og=perm(a);
og.clear();
og.resize(n,-1);
// for(auto x:og)
// {
// cout<<x<<' ';
// }
// cout<<endl;
for(int i=0;i<on;i++)og[st[i].second]=tmp[i];//cout<<i<<' '<<tmp[i]<<' '<<st[i].second<<endl;
// for(auto x:og)
// {
// cout<<x<<' ';
// }
// cout<<endl;
on=gg+1-kp;
st.clear();
for(int i=1;i<=on;i++)
{
// cout<<lo[n-i]<<' '<<n-i<<endl;
st.push_back({lo[n-i],n-i});
}
sort(begin(st),end(st));
for(int i=kp;i<=gg;i++)
{
// cout<<i<<' '<<tmp[i]<<' '<<st[i-kp].second<<endl;
og[st[i-kp].second]=tmp[i];
}
// for(auto x:og)
// {
// cout<<x<<' ';
// }
// cout<<endl;
vector<int>c(m+1,-s);
recur(0,n-1);
answer(c,x,y);
}
