#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 500005
int l[N],r[N],sz,now;
bool sw[N];
bitset<N> ch,out;
vector<int> c,x,y,pos[N];
map<int,int> mp,id;
int bi(int x){
int i=1;
while(i<x)i<<=1;
return i;
}
int bic(int x){
int i=1,cnt=0;
while(i<x)i<<=1,cnt++;
return cnt;
}
int cre(int lev){
int s=++sz;
if(lev==1){
l[s]=-1;
r[s]=-1;
return s;
}
l[s]=(cre(lev-1));
r[s]=(cre(lev-1));
return s;
}
void dfs(int s,int st,int head,vector<int> &a){
if(now<=0)return ;
if(!sw[s]){
sw[s]^=1;
if(l[s]==-1){
ch[s]=true;
int ps=pos[head].size();
if(now<=ps)l[s]=-a[pos[head][ps-now]+1];
else l[s]=st;
now--;
dfs(st,st,head,a);
}
else dfs(l[s],st,head,a);
}
else{
sw[s]^=1;
if(r[s]==-1){
int ps=pos[head].size();
if(now<=ps)r[s]=-a[pos[head][ps-now]+1];
else r[s]=st;
now--;
dfs(st,st,head,a);
}
else dfs(r[s],st,head,a);
}
}
void upd(int s,int st,int f,vector<int> &a){
if(ch[s]){
if(l[s]==st&&r[s]==st)l[s]=r[s]=f;
return ;
}
upd(l[s],st,s,a);
upd(r[s],st,s,a);
if(l[l[s]]==f&&r[l[s]]==f&&l[r[s]]==f&&r[r[s]]==f){
out[l[s]]=true;
l[s]=f;
out[r[s]]=true;
r[s]=f;
}
}
void create_circuit(int m,vector<int> a){
int i;
c.resize(m+1);
c[0]=a[0];
i=0;
for(auto x:a){
mp[x]++;
pos[x].push_back(i);
i++;
}
a.push_back(0);
for(auto [x,y]:mp){
if(mp[x]==1)c[x]=a[pos[x][0]+1];
else{
now=bi(y);
c[x]=-cre(bic(y));
dfs(-c[x],-c[x],x,a);
upd(-c[x],-c[x],x,a);
}
}
now=0;
for(i=1;i<=sz;i++)if(!out[i])id[i]=--now;
for(auto &x:c)if(x<0)x=id[-x];
for(i=1;i<=sz;i++){
if(l[i]>0)x.push_back(id[l[i]]);
else x.push_back(-l[i]);
if(r[i]>0)y.push_back(id[r[i]]);
else y.push_back(-r[i]);
}
answer(c,x,y);
}
