#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vll vector<ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;
vll res(200001), lef, rig;
void bintree(vll &a, vll &ind, ll x, ll pw, ll lim){
ll s_ind = lef.size()+1;
lef.pb(0), rig.pb(0);
if(pw == lim/2){
lef[s_ind-1] = a[ind[x]+1];
rig[s_ind-1] = a[ind[x+pw]+1];
return;
}
lef[s_ind-1] = lef.size()+1; lef[s_ind-1] *= -1;
bintree(a, ind, x, pw*2, lim);
rig[s_ind-1] = lef.size()+1; rig[s_ind-1] *= -1;
bintree(a, ind, x+pw, pw*2, lim);
}
vbool vis(200001);
void rec(vll &a, vector<vll> &ind, ll x){
// cout << x << endl;
vis[x] = 1;
if(ind[x].size() == 1){
// cout << 'p' << endl;
if(ind[x][0]+1 < a.size())res[x] = a[ind[x][0]+1];
// cout << 'p' << endl;
}else{
ll s_ind = lef.size()+1;
res[x] = -s_ind;
bintree(a, ind[x], 0, 1, ind[x].size());
}
for(ll i : ind[x]){
// cout << '>';
// cout << i << endl;
// cout << a.size() << endl;
if(i+1 == a.size())continue;
// cout << ' ' ;
// cout << a[i+1] << endl;
if(vis[a[i+1]])continue;
rec(a, ind, a[i+1]);
}
}
void create_circuit(int M, vector<int> A) {
// for(int i : A)cout << i << ' ';
// cout << endl;
ll m = M, n = A.size();
vll a(n); for(ll i = 0; i < n; i++) a[i] = A[i];
// cout << m << endl;
vector<vll> ind(m+1); for(ll i = 0; i < n; i++) ind[a[i]].pb(i);
res[0] = a[0];
rec(a, ind, a[0]);
// cout << "PPP" << endl;
// cout << n << ' ' << m << endl;
vector<int> ans(m+1);
for(ll i = 0; i <= m; i++){
// cout << res[i] << endl;
ans[i] = res[i];
}
// cout << "ppp" << endl;
vector<int> ans_l(lef.size()), ans_r(rig.size());
for(ll i = 0; i < lef.size(); i++){
ans_l[i] = lef[i]; ans_r[i] = rig[i];
// cout << i << ' ' << lef[i] << ' ' << rig[i] << endl;
}
// cout << "PPP" << endl;
answer(ans, ans_l, ans_r);
}
