#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;
if(og[l]==-1 and og[r]==-1)
{
lc=-p-1;
rc=-1;
}
else
{
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()+1;
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);
// for(auto x:lo)
// {
// cout<<x<<' ';
// }
// cout<<endl;
vector<pair<int,int>> st;
for(int i=1;i<=on;i++)
{
st.push_back({lo[n-i],n-i});
}
sort(begin(st),end(st));
// og=perm(a);
og.resize(n,-1);
for(int i=0;i<on;i++)og[st[i].second]=tmp[i];//,cout<<"putting "<<tmp[i]<<" on "<<st[i].second<<endl;
vector<int>c(m+1,-s);
recur(0,n-1);
answer(c,x,y);
}
