#include "doll.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(x...) qqbx(#x, x)
template <typename ...T> void qqbx(const char *s, T ...a) {
int cnt = sizeof...(T);
((std::cerr << "\e[1;32m(" << s << ") = ("), ... , (std::cerr << a << (--cnt ? ", " : "\e[0m)\n")));
}
#define pary(x...) danb(#x, x)
template <typename T> void danb(const char *s, T L, T R) {
std::cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
std::cerr << (f++ ? ", " : "") << *L;
std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
using namespace std;
const int maxn = 500025;
int odd[maxn];
int ls[maxn], rs[maxn];
int leaf[maxn];
int isLeaf[maxn];
int counter = 0;
int build(int l, int r, int a, int b) {
int cur = counter++;
if (l+1 == r) {
leaf[l] = cur;
isLeaf[cur] = b;
debug(cur, isLeaf[cur]);
return cur;
}
isLeaf[cur] = -1;
int m = l+(r-l)/2;
ls[cur] = build(l, m, a*2, b);
rs[cur] = build(m, r, a*2, b+a);
return cur;
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
vector<int> cnt(N + 1);
for (int i = 0; i < N; i++) cnt[A[i]] += 1;
vector<int> tmp;
for (int i = 0; i < N; i++) {
if (cnt[A[i]] != 1) {
tmp.push_back(i);
}
}
tmp.push_back(N);
pary(all(tmp));
int S = 0;
while ((1<<S) < (int)tmp.size()) ++S;
int root = build(0, 1 << S, 1, 0);
std::vector<int> C(M + 1);
std::vector<int> X(counter), Y(counter);
for (int i = 0; i <= M; i++) if (cnt[i] != 1) C[i] = -root-1;
for (int i = 0; i < N; i++) {
if (cnt[A[i]] == 1) {
C[A[i]] = i+1<N ? A[i+1] : -root-1;
debug(i);
}
}
for (int i = 0; i < counter; i++) {
if (isLeaf[i] != -1) {
if (isLeaf[i] < int(tmp.size())) {
X[i] = isLeaf[i] ? A[tmp[isLeaf[i]-1] + 1] : A[0];
} else {
X[i] = -root-1;
}
if (isLeaf[i] == (1<<S) - 1) {
Y[i] = 0;
} else {
Y[i] = -root-1;
}
} else {
X[i] = -ls[i]-1;
Y[i] = -rs[i]-1;
}
}
/*
int cur = root;
do {
if (isLeaf[cur] != -1) {
debug(cur, isLeaf[cur], odd[cur]);
// pary(odd, odd+counter);
}
int nxt = odd[cur] ? rs[cur] : ls[cur];
odd[cur] ^= 1;
cur = nxt;
} while (accumulate(odd, odd+counter, 0) != 0);
*/
answer(C, X, Y);
}
