#include "doll.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int WRONG_ID = -16969420, ROOT_ID = WRONG_ID + 1;
vector<int> arr;
vector<int> x, y;
pair<int, int> buildTree(int l, int r) {
if(l == r) {
return {arr[l], arr[l] != ROOT_ID};
}
int m = (l + r) / 2ll;
auto lftSon = buildTree(l, m);
auto rghtSon = buildTree(m + 1, r);
//cout << l << " " << r << " " << lftSon << " " << rghtSon << endl;
if(lftSon.second + rghtSon.second == 0) {
return {0, ROOT_ID};
} else {
x.push_back(lftSon.first);
y.push_back(rghtSon.first);
return {-x.size(), lftSon.second + rghtSon.second};
}
}
int bitInverse(int ind, int pow2) {
int ret = 0;
for(int i = 0; i < pow2; i ++) {
if(ind & (1 << i)) {
ret |= (1 << (pow2 - 1 - i));
}
}
return ret;
}
void create_circuit(int M, std::vector<int> A) {
arr = A;
arr.push_back(ROOT_ID);
int pow2 = 0;
while((1 << pow2) < arr.size()) {
pow2 ++;
}
while(arr.size() < (1 << pow2)) {
arr.push_back(ROOT_ID);
}
arr[arr.size() - 1] = 0;
vector<pair<int, int> > prs;
for(int i = 0; i < arr.size(); i ++) {
int inv = bitInverse(i, pow2);
prs.push_back({inv, arr[i]});
}
sort(prs.begin(), prs.end());
for(int i = 0; i < arr.size(); i ++) {
arr[i] = prs[i].second;
}
pow2 = 1 << pow2;
int root = buildTree(0, pow2 - 1).first;
vector<int> ptr;
for(int i = 0; i <= M; i ++) {
ptr.push_back(root);
}
for(auto it : ptr) {
// cout << it << " ";
}
//cout << endl;
for(int i = 0; i < x.size(); i ++) {
//cout << -i - 1 << " " << x[i] << " " << y[i] << endl;
if(x[i] == ROOT_ID) {
x[i] = root;
}
if(y[i] == ROOT_ID) {
y[i] = root;
}
}
answer(ptr, x, y);
}
