#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define SIZE(x) (int)x.size()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define pb push_back
typedef vector<int> vi;
vi L, R, v, state;
int t=1, skip, s=-1;
void build(int u, int l, int r) {
L.pb(0), R.pb(0), v.pb(0);
assert(u>=0 && u<SIZE(v));
if(l>r) {
v[u]=-1;
return;
}
if(skip>0 && r-l+1<=skip) {
v[u]=-1;
skip-=r-l+1;
return;
}
if(l==r) return;
v[u] = s--;
int m=(l+r)/2;
L[u] = t++;
build(L[u], l, m);
R[u] = t++;
build(R[u], m+1, r);
}
bool dfs(int u, int a) {
assert(u>=0 && u<SIZE(v));
if(u!=0 && v[u]==-1) return false;
if(!v[u]) {
v[u]=a;
return true;
}
state[u]^=1;
assert(v[L[u]]!=-1 || v[R[u]]!=-1);
if(state[u]) return dfs(L[u],a);
return dfs(R[u],a);
}
bool first_subtasks(int m, vi a) {
vi c(m+1),x,y;
map<int,vi> next;
int n=SIZE(a);
a.pb(0);
forn(i,n) next[a[i]].pb(a[i+1]);
c[0]=a[0];
int j=0;
for(auto &p:next) {
auto [a,v] = p;
int S=SIZE(v);
if(S==1) {
c[a] = v[0];
} else if(S==2) {
c[a] = --j;
x.pb(v[0]);
y.pb(v[1]);
continue;
} else if(S==4) {
c[a] = --j;
x.pb(--j);
y.pb(--j);
x.pb(v[0]);
y.pb(v[2]);
x.pb(v[1]);
y.pb(v[3]);
continue;
} else if(S==3) {
c[a] = --j;
x.pb(--j);
y.pb(--j);
x.pb(v[0]);
y.pb(v[1]);
x.pb(j+2);
y.pb(v[2]);
} else {
return false;
}
}
answer(c,x,y);
return true;
}
void create_circuit(int m, vi A) {
if(first_subtasks(m,A)) return;
vi c(m+1);
c[0]=A[0];
forsn(i,1,m+1) c[i]=-1;
int n=SIZE(A), sz=1;
while(sz<n) sz*=2;
assert(sz>=n);
skip = sz-n;
build(0,1,sz);
assert(SIZE(L)==SIZE(R) && SIZE(v)==SIZE(L));
vi a;
forsn(i,1,n) a.pb(A[i]);
a.pb(0);
state.assign(SIZE(v),0);
forn(i,n) {
bool flag=0;
while(!flag) flag=dfs(0,a[i]);
}
vi x, y;
int mini=-1;
forn(i,SIZE(v)) {
if(L[i] && R[i]) {
x.pb(v[L[i]]);
y.pb(v[R[i]]);
mini=min({mini,v[L[i]],v[R[i]]});
}
}
if(SIZE(x)<-mini) {
x.resize(-mini,-1);
y.resize(-mini,-1);
}
answer(c,x,y);
}
