#include "doll.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
namespace{
int n, m, cnt = 1;
vector<int> c, x, y;
int sl, sr;
vector<pair<pair<int, int>, int>> leaves;
int build(int l, int r, int ind, int dep, bool flag){
if(r < sl){
return 1;
}
if(l == r){
leaves.push_back(make_pair(make_pair(ind, cnt - 1), (int)flag));
return 0;
}
int mid = (l + r) >> 1;
int cur = cnt;
cnt++;
x[cur - 1] = -build(l, mid, ind, dep + 1, 0);
y[cur - 1] = -build(mid + 1, r, ind + (1 << dep), dep + 1, 1);
return cur;
}
}
void create_circuit(int M, std::vector<int> A){
m = M;
n = A.size();
c.resize(m + 1);
x.resize(n + 50);
y.resize(n + 50);
fill(x.begin(), x.end(), 12345678);
fill(y.begin(), y.end(), 12345678);
int dep = 1;
while((1 << dep) < n) dep++;
sr = (1 << dep);
sl = sr - n + 1;
int fst = A[0];
c[fst] = -build(1, sr, 0, 0, 0);
c[0] = fst;
sort(leaves.begin(), leaves.end());
reverse(leaves.begin(), leaves.end());
A.push_back(0);
reverse(A.begin(), A.end());
A.pop_back();
int sz = (int)leaves.size();
for(int i = 1; i <= m; i++) c[i] = c[fst];
for(int i = 0; i < n; i++){
auto &[leaf, flag] = leaves[i];
//cout << leaf.first << ' ' << leaf.second << " " << A[i] << "\n";
if(flag == 0) x[leaf.second - 1] = A[i];
else y[leaf.second - 1] = A[i];
}
for(int i = n; i < sz; i++){
auto &[leaf, flag] = leaves[i];
if(flag == 0) x[leaf.second - 1] = c[fst];
else y[leaf.second - 1] = c[fst];
}
while(!x.empty() && x.back() == 12345678) x.pop_back();
while(!y.empty() && y.back() == 12345678) y.pop_back();
/*for(auto &hi: c) cout << hi << ' ';
cout << "\n";
for(auto &hi: x) cout << hi << " ";
cout << "\n";
for(auto &hi: y) cout << hi << " ";
cout << "\n";*/
answer(c, x, y);
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp doll.cpp
