#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;
const ll MAXN = 2e5+5;
const ll INF = 1e9+7;
void create_circuit(int M, std::vector<int> A) {
int n = A.size(),k,S=-1,i,j,bruh;
vector<vector<int>>adj(M+5);
std::vector<int> X, Y;
std::vector<int> C(M + 1);
C[0]=A[0];
for(i=0;i<n-1;i++){
//C[A[i]]=A[i+1];
adj[A[i]].pb(A[i+1]);
}
adj[A[n-1]].pb(0);
for(i=1;i<=M;i++){
k=adj[i].size(); S=-(X.size())-1;
// cout<<i<<" #"<<k<<endl;
if(k==1){
C[i]=adj[i][0];
}else if(k>=2){
ll cur=1,mock=1; bruh=0;
C[i] = S;
while(cur<k){//new level com cur switches
// cout<<cur<<"jj\n";
for(j=0;j<cur;j++){
if(2*cur<k){//ainda vai haver next
X.pb(-(2*mock)+S+1);
Y.pb(-(2*mock+1)+S+1);//cout<<-(2*mock)-1<<" "<<-(2*mock+1)-1<<endl;
}else{
ll a=mock,siga=0,po=bruh;
while(po>0){po--;
if(a&(1LL<<0))siga|=(1LL<<po);
a/=2;
}
//cout<<siga<<" "<<cur<<endl;
if(siga<k){
X.pb(adj[i][siga]);
}else{
X.pb(C[i]);
}
if(siga+cur<k-1){
Y.pb(adj[i][siga+cur]);
}else if(siga+cur==2*cur-1){
Y.pb(adj[i][k-1]);
}else{
Y.pb(C[i]);
}
}
mock++;
}
cur*=2;bruh++;
}
}
}
/*
for(i=0;i<=M;i++)cout<<C[i]<<" ";
cout<<endl;
for(auto u:X)cout<<u<<" ";
cout<<endl;
for(auto u:Y)cout<<u<<" ";
cout<<endl;
*/
answer(C, X, Y);
}
