#include "doll.h"
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
constexpr int H = 18;
vector<vector<int>> graph;
vector<int> C, X, Y;
int nxt = -1;
array<vector<int>, H> pos;
void create(int curr, int sz, vector<int> v, int root, int h) {
// For local vectors
curr = -1-curr;
if (sz == 2) {
X[curr] = v.size() > 1 ? v[0] : root;
Y[curr] = v.size() > 1 ? v[1] : v[0];
} else {
if (v.size() > sz/2) {
X[curr] = nxt--;
Y[curr] = nxt--;
vector<int> i1(pos[h].end() - v.size(), pos[h].begin() + sz/2), i2(pos[h].begin() + sz/2, pos[h].end()), v1, v2;
sort(i1.begin(), i1.end());
sort(i2.begin(), i2.end());
int i = 0, j = 0, x = 0;
while (i < v1.size() || j < i2.size()) {
if (i < i1.size() && (j == i2.size() || i1[i] < i2[j])) {
i1[i++] = x++;
} else {
i2[j++] = x++;
}
}
for (int i: i1) v1.push_back(v[i]);
for (int i: i2) v2.push_back(v[i]);
create(X[curr], sz/2, v1, root, h-1);
create(Y[curr], sz/2, v2, root, h-1);
} else {
X[curr] = root;
Y[curr] = nxt--;
create(Y[curr], sz/2, v, root, h-1);
}
}
}
void calc_recur(vector<int> v, int h, int i) {
if (v.size() == 1) {
pos[h][i] = v[0];
return;
}
vector<int> v1, v2;
for (int i = 0; i < v.size(); i++) {
if (i % 2 == 0) v1.push_back(v[i]);
else v2.push_back(v[i]);
}
calc_recur(v1, h, i);
calc_recur(v2, h, i + v2.size());
}
void create_circuit(int M, vector<int> A) {
// SETUP
for (int h = 0; h < H; h++) {
pos[h].resize(1 << h);
vector<int> v;
v.resize(1 << h);
for (int i = 0; i < (1 << h); i++) v[i] = i;
calc_recur(v, h, 0);
}
const int N = A.size();
graph.resize(M+1);
int last = 0;
for (int i = 0; i < N; i++) {
graph[last].push_back(A[i]);
last = A[i];
}
graph[last].push_back(0);
C.resize(M+1);
X.resize(400'000);
Y.resize(400'000);
for (int i = 0; i < M+1; i++) {
if (graph[i].size() == 0) {
C[i] = 0;
} else if (graph[i].size() == 1) {
C[i] = graph[i][0];
} else {
int sz = 1, h = 0;
while (sz < graph[i].size()) {
h++;
sz *= 2;
}
C[i] = nxt--;
create(C[i], sz, graph[i], C[i], h);
}
}
X.resize(-1-nxt);
Y.resize(-1-nxt);
answer(C, X, Y);
}
