// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
map<int, pair<int, int>> sw;
int64_t h(int a, int b) {
return (1ll*a*1e9)+b;
}
vector<int> get_ord(vector<vector<pair<int, bool>>>& tree, int root) {
vector<bool> state(root+1, false);
vector<bool> had(root+1, false);
bool done = false;
vector<int> ret;
auto dfs = [&] (auto&& self, int v, bool fake) -> void {
if (!tree[v].size()) {
if (fake) return;
if (had[v]) {
done = true;
return;
}
had[v] = true;
ret.push_back(v);
return;
}
if (!state[v]) {
self(self, tree[v][0].first, tree[v][0].second);
}
else {
self(self, tree[v][1].first, tree[v][1].second);
}
state[v] = state[v] ^ 1;
};
while (!done) dfs(dfs, root, false);
return ret;
}
int build_top_down(int cnt_leaves, int shift, vector<int>& conns) {
vector<vector<pair<int, bool>>> tree(4*cnt_leaves);
int now = 0;
vector<pair<int, bool>> inds;//ind, fake
for (int i = 0; i < cnt_leaves; ++i) {
inds.push_back({now++, false});
}
while (inds.size() > 1) {
vector<pair<int, bool>> nxt_inds;
for (int i = 0; i < inds.size(); i += 2) {
tree[now].push_back(inds[i]);
tree[now].push_back(inds[i+1]);
nxt_inds.push_back({now++, false});
}
if (nxt_inds.size() != 1 && nxt_inds.size() % 2 != 0) {
reverse(nxt_inds.begin(), nxt_inds.end());
nxt_inds.push_back({now++, true});
reverse(nxt_inds.begin(), nxt_inds.end());
}
inds.swap(nxt_inds);
}
int root = inds[0].first;
vector<int> ret = get_ord(tree, root);
vector<int> place(cnt_leaves);
for (int i = 0; i < cnt_leaves; ++i) {
place[ret[i]] = i;
}
shift += cnt_leaves;
auto get = [&] (int ind) -> int {
return shift+(-ind);
};
for (int i = 0; i < cnt_leaves; ++i) {
if (conns[i] < 0) conns[i] = get(root);
}
auto fill_sw = [&] (auto&& self, int v, bool fake) -> void {
if (fake) {
sw[get(v)].first = get(root);
sw[get(v)].second = get(root);
return;
}
if (tree[v].front().first < cnt_leaves) {
sw[shift+(-v)].first = conns[place[tree[v].front().first]];
sw[shift+(-v)].second = conns[place[tree[v].back().first]];
return;
}
sw[get(v)].first = get(tree[v].front().first);
sw[get(v)].second = get(tree[v].back().first);
self(self, tree[v].front().first, tree[v].front().second);
self(self, tree[v].back().first, tree[v].back().second);
};
fill_sw(fill_sw, root, false);
return get(root);
}
void create_circuit(int M, std::vector<int> A) {
vector<int> C(M+1);
vector<vector<int>> graph(M+1);
const int n = A.size();
graph[0].push_back(A[0]);
for (int i = 0; i < n-1; ++i) {
graph[A[i]].push_back(A[i+1]);
}
graph[A[n-1]].push_back(0);
int nxt_free = -1;
for (int i = 0; i <= M; ++i) {
vector<int>& conns = graph[i];
if (!conns.size()) {
C[i] = 0;
continue;
}
if (conns.size() == 1) {
C[i] = conns.front();
continue;
}
reverse(conns.begin(), conns.end());
if (conns.size() % 2 != 0) conns.push_back(nxt_free);
reverse(conns.begin(), conns.end());
int root = build_top_down(conns.size(), nxt_free, conns);
C[i] = root;
nxt_free = root - 1;
}
vector<int> X, Y;
for (int i = -1; i > nxt_free; --i) {
X.push_back(sw[i].first);
Y.push_back(sw[i].second);
}
answer(C, X, Y);
}
