#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int m,n;
std::vector<int> C;
int num;
vector <int> X,Y;
int times[400004];
const int inf = 1e7;
void solve(int v, int from, int to)
{
// cout<<v<<" "<<from<<" "<<to<<endl;
X.push_back(-1);
Y.push_back(-1);
int mid = (from+to)/2;
if(from<mid&&from<n)
{
num++;
Y[v]=-num-1;
solve(num,from,mid);
}
else
{
if(n<=from)Y[v] = inf;
else
Y[v]=-1;
}
if(mid+1<to&&mid+1<n)
{
num++;
X[v]=-num-1;
solve(num,mid+1,to);
}
else
{if(n<=mid+1)X[v] = inf;
else
X[v]=-1;
}
return ;
}
void create_circuit(int _M, std::vector<int> _A) {
a = _A;
a.push_back(0);
n = a.size();
m = _M;
C.resize(m+1);
C[0] = -1;
for (int i = 1; i <= m; ++i) {
C[i] = -1;
}
int br = 1;
while(br<n)br*=2;
solve(0, 0, br-1);
int c = 0;
int x = 0;
while(c<n)
{
times[x]++;
if(times[x]%2==1)
{
if(X[x]==-1)
{
X[x] = a[c];
c++;
x = 0;
}
else
{
x = -X[x]-1;
}
}
else
{
if(Y[x]==-1)
{
Y[x] = a[c];
c++;
x = 0;
}
else
{
x = -Y[x]-1;
}
}
if(x==-inf-1)x=0;
} //for(int i=0;i<=num;i++)
/// {
///cout<<i<<": "<<X[i]<<" "<<Y[i]<<endl;
//}
for(int i=0;i<=num;i++)
{
if(X[i]==inf)X[i] = -1;
if(Y[i]==inf)Y[i]=-1;
}
//cout<<"YEs"<<endl;
answer(C, X, Y);
}
/*#include <bits/stdc++.h>
using namespace std;
void answer(vector<int> C, vector<int> X, vector<int> Y);
vector<int> C, X, Y;
const int _N = 1e6 + 7;
int B[_N][2], timer[_N], cnt, n, m, k = 0;
int f(int s, int e){
if(n <= s){
return 1;
}
if(s == e){
return -1;
}
int m = (s + e) / 2, c = ++k;
B[c][1] = f(s, m);
B[c][0] = f(m + 1, e);
return c;
}
void create_circuit(int M, vector<int> A){
for(int i = 0; i < M; i++){
C.push_back(-1);
}
C.push_back(-1);
A.push_back(0);
n = (int)A.size();
m = M;
int t = 1;
while(t < n){
t *= 2;
}
f(0, t - 1);
for(int i = 1, c = 0; c < n;){
int &x = B[i][timer[i] & 1];
++timer[i];
if(x < 0){
x = -A[c++];
i = 1;
continue;
}
i = x;
}
for(int i = 1; i <= k; i++){
X.push_back(-B[i][0]);
Y.push_back(-B[i][1]);
}
for(int i=0;i<X.size();i++)
{
cout<<i<<": "<<X[i]<<" "<<Y[i]<<endl;
}
answer(C, X, Y);
}
*/
