#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int Nmax=200010;
int M, N, A[Nmax];
int cnt, p, vs, siz, out[Nmax];
vector<int> V[Nmax];
unordered_map<int, int> l, r;
unordered_map<int, bool> st;
void DFS_Construct(int curr, int s, int e) {
if(e-s==1) {
l[curr]=r[curr]=INT_MAX;
if(s<=siz-vs) r[curr]=out[p];
return;
}
int m=(s+e)/2;
l[curr]=--cnt;
DFS_Construct(l[curr], s, m);
if(m<=siz-vs) r[curr]=out[p];
else {
r[curr]=--cnt;
DFS_Construct(r[curr], m+1, e);
}
}
void DFS_Connect(int curr, int k) {
st[curr]^=1;
if(!st[curr]) {
if(r[curr]==INT_MAX) {
r[curr]=V[p][k];
return;
}
DFS_Connect(r[curr], k);
}
else {
if(l[curr]==INT_MAX) {
l[curr]=V[p][k];
return;
}
DFS_Connect(l[curr], k);
}
}
void create_circuit(int M, vector<int> A) {
ios_base::sync_with_stdio(0); cin.tie(0);
N=A.size();
V[0].push_back(A[0]);
for(int i=0; i<N; i++) V[A[i]].push_back(A[i+1]);
for(int i=0; i<=M; i++) if(V[i].size()) {
if(V[i].size()==1) {
out[i]=V[i][0];
continue;
}
p=i, vs=V[i].size(), siz=(1<<(32-__builtin_clz(V[i].size()-1)));
out[i]=--cnt;
DFS_Construct(out[i], 1, siz);
for(int j=0; j<V[i].size(); j++) DFS_Connect(out[i], j);
}
vector<int> C, X, Y;
for(int i=0; i<=M; i++) C.push_back(out[i]);
for(int i=-1; i>=cnt; i--) {
X.push_back(l[i]); Y.push_back(r[i]);
}
answer(C, X, Y);
}
