#include "doll.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int switches=0;
int out[400005];
int fiu1[400005];
int fiu2[400005];
vector<int>indicii;
void solve(int node,int sz,vector<int>vec,int index,int pw)
{
if(sz==2)
{
indicii.push_back(index);
indicii.push_back(index+pw);
return;
}
int mij=(sz)/2;
vector<int>st;
vector<int>dr;
int f1=0,f2=0;
for(int i=0;i<vec.size();i++)
{
if(vec[i]<0)
{
if(st.size()<mij)
{
f1++;
st.push_back(vec[i]);
}
else
{
f2++;
dr.push_back(vec[i]);
}
}
else
{
if(dr.size()<st.size())
{
dr.push_back(vec[i]);
}
else
{
st.push_back(vec[i]);
}
}
}
if(f1!=mij)
{
switches++;
fiu1[-node]=-switches;
solve(fiu1[-node],mij,st,index,pw*2);
}
else
{
fiu1[-node]=vec[0];
}
switches++;
fiu2[-node]=-switches;
solve(fiu2[-node],mij,dr,index+pw,pw*2);
}
void add(int node,int index,int val,int st,int dr)
{
if(st+1==dr)
{
if(index==0)
{
fiu1[-node]=val;
}
else
{
fiu2[-node]=val;
}
return;
}
int mij=(st+dr)/2;
if(index%2==0)
{
add(fiu1[-node],index/2,val,st,mij);
}
else
{
add(fiu2[-node],index/2,val,mij+1,dr);
}
}
void make(vector<int>copii)
{
indicii.clear();
switches++;
int out=-switches;
int adev=copii.size();
reverse(copii.begin(),copii.end());
while(__builtin_popcount(copii.size())!=1)
{
copii.push_back(out);
}
int fals=copii.size()-adev;
reverse(copii.begin(),copii.end());
solve(out,copii.size(),copii,0,1);
sort(indicii.begin(),indicii.end());
int off=0;
if(fals%2==1)
{
off=1;
}
else
{
off=0;
}
for(int i=fals-off;i<copii.size();i++)
{
add(out,indicii[i-(fals-off)],copii[i],0,copii.size()-1);
}
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
A.push_back(0);
make(A);
vector<int>C,X,Y;
for(int i=0;i<=M;i++)
{
out[i]=-1;
C.push_back(out[i]);
//cout<<i<<" "<<out[i]<<'\n';
}
for(int i=1;i<=switches;i++)
{
X.push_back(fiu1[i]);
Y.push_back(fiu2[i]);
//cout<<-i<<" x: "<<fiu1[i]<<" y: "<<fiu2[i]<<'\n';
}
answer (C,X,Y);
}
