#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, s;
vi c, x, y, a, state;
vector<vi> nxt;
int LOG2(int X) {
RE(i,30) if((1<<i) >= X) return i;
}
int createTriangle(int size) {
if(size == 0) return 0;
int i=s++;
int id=-s;
x.pb(0);
y.pb(0);
state.pb(0);
int nx = createTriangle(size-1);
int ny = createTriangle(size-1);
x[i] = nx;
y[i] = ny;
return id;
}
int setTriangle(int u, int value) {
u = -1-u;
if(state[u]) {
if(y[u] == 0) y[u] = value;
else setTriangle(y[u], value);
} else {
if(x[u] == 0) x[u] = value;
else setTriangle(x[u], value);
}
state[u] = !state[u];
}
void create_circuit(int m, vi A) {
a = A;
s = 0;
n = a.size();
c.clear(); x.clear(); y.clear(); nxt.clear(); state.clear();
c.resize(m+1);
nxt.resize(m+1);
nxt[0].pb(a[0]);
RE(i,n) nxt[a[i]].pb(i==n-1 ? 0 : a[i+1]);
RE(i,m+1) {
int l2 = LOG2(nxt[i].size());
c[i] = createTriangle(l2);
if(nxt[i].size() == 1) c[i] = nxt[i][0];
else if(nxt[i].size() != 0) {
int empty = (1<<l2) - nxt[i].size();
RE(j,empty) setTriangle(c[i],c[i]);
RE(j,nxt[i].size()) setTriangle(c[i], nxt[i][j]);
}
}
answer(c, x, y);
}
