#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> C;
vector<int> X;
vector<int> Y;
int swidc = 0;
int new_switch() {
X.push_back(0);
Y.push_back(0);
return -(++swidc);
}
int br(size_t sid, size_t count, int killd, const vector<int>& dests) {
if (count == 1) {
if (sid < dests.size()) {
return dests[sid];
} else {
return killd;
}
}
int cursw = new_switch();
size_t half = count / 2;
int lc = br(sid, half, killd, dests);
int rc = br(sid + half, half, killd, dests);
X[-cursw - 1] = lc;
Y[-cursw - 1] = rc;
return cursw;
}
int cs(const vector<int>& dests) {
size_t k = dests.size();
if (k == 0) return 0;
if (k == 1) return dests[0];
size_t m = 1;
while (m < k) {
m *= 2;
}
int rtsw = new_switch();
size_t half = m / 2;
int lc = br(0, half, rtsw, dests);
int rc = br(half, half, rtsw, dests);
X[-rtsw - 1] = lc;
Y[-rtsw - 1] = rc;
return rtsw;
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
C.assign(M + 1, 0);
if (N == 0) {
answer(C, X, Y);
return;
}
map<int, vector<int>> occs;
for (int i = 0; i < N; ++i) {
occs[A[i]].push_back(i);
}
C[0] = A[0];
for (int t = 1; t <= M; ++t) {
if (occs.find(t) == occs.end()) {
C[t] = 0;
continue;
}
const auto& pos = occs.at(t);
vector<int> des;
des.reserve(pos.size());
for (int pos : pos) {
des.push_back((pos == N - 1) ? 0 : A[pos + 1]);
}
C[t] = cs(des);
}
answer(C, X, Y);
}
