#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int idd;
int n, m;
vector<int> a;
vector<int> x, y;
void build(const int root, int nd, int l, int r, vector<int> cur, bool left) {
if (l == r) {
return;
}
vector<int> lx, rx;
for (int i = 0; i < (int) cur.size(); ++i) {
if (i % 2 == 0) {
lx.push_back(cur[i]);
} else {
rx.push_back(cur[i]);
}
}
int mid = (l + r) >> 1;
//if (!left && rx.empty()) {
//swap(lx, rx);
//}
//cerr << "lx: ";
//for (int i : lx) {
//cerr << i << ' ';
//}
//cerr << '\n';
//cerr << "rx: ";
//for (int i : rx) {
//cerr << i << ' ';
//}
//cerr << '\n';
assert(!lx.empty() && !rx.empty());
if (l < mid) {
x[-nd - 1] = --idd;
x.push_back(0);
y.push_back(0);
build(root, idd, l, mid, lx, true);
} else {
if (lx[0] == -1) {
x[-nd - 1] = root;
} else {
x[-nd - 1] = a[lx[0] + 1];
}
}
if (mid + 1 < r) {
y[-nd - 1] = --idd;
x.push_back(0);
y.push_back(0);
build(root, idd, mid + 1, r, rx, left);
} else {
if (rx[0] == -1) {
y[-nd - 1] = root;
} else {
y[-nd - 1] = a[rx[0] + 1];
}
}
}
void create_circuit(int m_, vector<int> a_) {
m = m_;
a = a_;
n = (int) a.size();
a.insert(a.begin(), 0);
a.push_back(0);
vector<vector<int>> occ(m + 1);
for (int i = 0; i < n + 1; ++i) {
occ[a[i]].push_back(i);
}
idd = 0;
vector<int> c;
c.resize(m + 1);
for (int i = 0; i <= m; ++i) {
int sz = occ[i].size();
if (!sz) {
continue;
}
if (sz == 1) {
c[i] = a[occ[i][0] + 1];
continue;
}
int lg = 32 - __builtin_clz(sz);
if ((sz & (sz - 1)) == 0) {//power of two
lg--;
}
int leaves = 1 << lg;
vector<int> o;
for (int j = 0; j < leaves - sz; ++j) {
o.push_back(-1);
}
for (int j : occ[i]) {
o.push_back(j);
}
c[i] = --idd;
x.push_back(0);
y.push_back(0);
build(idd, idd, 1, leaves, o, 0);
}
//cerr << "occ[1]: ";
//for (int j : occ[1]) {
//cerr << j << ' ';
//}
//cerr << '\n';
//cerr << "C: ";
//for (int i = 0; i <= m; ++i) {
//cerr << c[i] << " \n"[i == m];
//}
//cerr << "X: ";
//for (int i = 0; i < -idd; ++i) {
//cerr << x[i] << " \n"[i == -idd - 1];
//}
//cerr << "Y: ";
//for (int i = 0; i < -idd; ++i) {
//cerr << y[i] << " \n"[i == -idd - 1];
//}
answer(c, x, y);
}
