#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using bdata = vector<bool>;
using di = pair<int, int>;
using vd = vector<di>;
struct SegTree {
idata treeIds;
int rsize = 0;
int start, height, size;
void generate (int node, int limit) {
if (node == 0) return ;
generate(node >> 1, (limit + 1) >> 1);
if (node == start) return ;
for (int u = node; u < node + limit; u ++)
treeIds[u] = - ((rsize ++) + 1);
}
int getId (int node) {
int count = 0;
int diam = height - 1;
while (node != 1) {
if (node & 1) count += 1 << diam;
diam --;
node >>= 1;
}
return count;
}
idata X, Y;
SegTree (idata A) {
size = A.size();
height = ceil(log2(size + 1));
start = 1 << height;
treeIds.resize(start << 1, - 1e9);
generate(start, size);
vd g_pos;
for (int i = 0; i < size; i ++)
g_pos.push_back({ getId( i + start ), i + start });
sort(g_pos.begin(), g_pos.end());
for (int i = 0; i < size; i ++)
treeIds[g_pos [i].second] = A[i];
X.resize(rsize); Y.resize(rsize);
for (int i = 1; i < start; i ++) {
if (treeIds[i] >= 0 || treeIds[i] == - 1e9) continue ;
int xid = - (1 + treeIds[i]);
int n0 = 2 * i; int vn0 = treeIds[n0] == - 1e9 ? -1 : treeIds[n0];
int n1 = 2 * i + 1; int vn1 = treeIds[n1] == - 1e9 ? -1 : treeIds[n1];
X[xid] = vn0;
Y[xid] = vn1;
}
}
};
void create_circuit(int M, vector<int> A) {
idata C( M + 1, - 1 ); // - 1 is the decision tree root
SegTree tree(A);
idata X = tree.X;
idata Y = tree.Y;
int h = 1;
int p = 0;
while (h < tree.start) {
if (tree.treeIds[h * 2 + 1] == - 1e9) {
Y[p] = h * 2 + 1 >= tree.start ? 0 : - ((tree.rsize ++) + 1);
if (Y[p] != 0) {
X.push_back(-1);
Y.push_back(-1);
}
}
h = (h * 2) + 1;
p = - (Y[p] + 1);
}
answer(C, X, Y);
}
