#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
#define ALL(x) begin(x), end(x)
#define loop(n, i) for (int i = 0; i < n; i++)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
int INF = 1e9;
int swi(int x)
{
return -x - 1;
}
void create_circuit(int M, vi A)
{
int N = sz(A);
const int L = __lg(N) + 2;
vvi trees(L);
for (int i = 1, cnt = 2; i < L; i++)
{
// cnt - 1 switches indexed 1 .. cnt-1
vb x(cnt);
while (sz(trees[i]) < cnt)
{
int j = 1;
while (j < cnt)
{
x[j].flip();
if (!x[j])
j = 2 * j + 1;
else
j *= 2;
}
trees[i].pb(j - cnt);
}
cnt *= 2;
}
vvi nxt(M + 1); // volgende
A.pb(0);
loop(N, ix)
{
nxt[A[ix]].pb(A[ix + 1]);
}
vi C(M + 1, -1);
C[0] = A[0];
int S = 0;
vi X, Y;
vi curOcc(M + 1);
loop(N, i)
{
if (sz(nxt[A[i]]) == 1)
{
C[A[i]] = A[i + 1];
}
else
{
if (curOcc[A[i]] == 0)
{
int log = 1;
int power = 2;
int k = sz(nxt[A[i]]);
while (power < k)
{
log++;
power *= 2;
}
int startIx = S;
S += power - 1;
loop(power - 1, ix)
{
X.pb({});
Y.pb({});
}
C[A[i]] = swi(startIx);
const auto &perm = trees[log];
vector<int *> leaves;
for (int ix = 0; ix < power - 1; ix++)
{
int iy = ix + startIx;
int l = 2 * ix + 1, r = 2 * ix + 2;
X[iy] = swi(l + startIx), Y[iy] = swi(r + startIx);
if (ix >= power / 2 - 1)
{
leaves.push_back(&X[iy]);
leaves.push_back(&Y[iy]);
}
}
for (auto l : leaves)
*l = swi(startIx);
for (int ix = 0; ix < k - 1; ++ix)
{
int want = perm[ix];
*leaves[want] = nxt[A[i]][ix];
}
*leaves.back() = nxt[A[i]].back();
}
}
curOcc[A[i]]++;
}
for (int &i : C)
if (i == -1 && S == 0)
i = 0;
for (int i : C)
if (i < -S || i > M)
throw;
for (int i : X)
if (i < -S || i > M)
throw;
for (int i : Y)
if (i < -S || i > M)
throw;
answer(C, X, Y);
}
