#include "bits/stdc++.h"
#include "doll.h"
using namespace std;
void create_circuit(int M, vector<int> A)
{
int N = A.size();
vector<int> C(M + 1, -1);
vector<int> X, Y;
vector<int> move(6e5);
vector<vector<int>> g(M + 1);
for (int i = 0; i < N; i++)
g[0].push_back(A[i]);
for (int i = 0; i < N - 1; i++)
if (A[i] == A.back())
g[A[i]].push_back(-1);
g[A.back()].push_back(0);
for (int i = 0; i <= M; i++)
{
int sz = g[i].size();
if (sz == 0)
continue;
if (sz == 1)
{
C[i] = g[i][0];
continue;
}
int x = 0;
while ((1ll << x) < sz)
x++;
int ind = X.size() + 1;
ind *= -1;
C[i] = ind;
int r = 0;
reverse(g[i].begin(), g[i].end());
while (sz < (1ll << x))
sz++, g[i].push_back(ind), r++;
reverse(g[i].begin(), g[i].end());
auto build = [&](auto build, int L, int R) -> void
{
if (L == R - 1)
{
X.push_back(1e9), Y.push_back(1e9);
if (L < r)
X.back() = ind;
if (R < r)
Y.back() = ind;
}
else
{
int a = X.size() + 1;
X.push_back(ind);
Y.push_back(-a - 1);
int m = (L + R) / 2;
build(build, m + 1, R);
if (m < r)
return;
X[a - 1] = -(X.size() + 1);
build(build, L, m);
}
};
build(build, 0, sz - 1);
for (int x = r; x < sz; x++)
{
int pv = -1;
int cur = -ind;
while (abs(cur) != 1e9)
pv = cur, cur = -((move[cur]++) % 2 ? Y[cur - 1] : X[cur - 1]);
if (move[pv] % 2)
X[pv - 1] = g[i][x];
else
Y[pv - 1] = g[i][x];
}
}
answer(C, X, Y);
}
