#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){
if(ind[x]+1 < a.size()) lef[s_ind-1] = a[ind[x]+1];
if(ind[x+pw]+1 < a.size())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, ll l, ll r){
// cout << x << endl;
auto it1 = lower_bound(ind[x].begin(), ind[x].end(), l);
auto it2 = lower_bound(ind[x].begin(), ind[x].end(), r+1);
ll sz = it2 - it1;
ll st = it1-ind[x].begin();
ll en = it2-ind[x].begin();
// for(ll i : ind[x])cout << i << ' ';
// cout << endl;
// cout << st << ' ' << en << ' ' << sz << endl;
// cout << l << ' ' << r << endl;
vis[x] = 1;
if(sz == 1){
// cout << 'p' << endl;
if(ind[x][st]+1 < a.size())res[x] = a[ind[x][st]+1];
// cout << 'p' << endl;
}else{
ll s_ind = lef.size()+1;
res[x] = -s_ind;
bintree(a, ind[x], st, 1, sz);
}
for(ll i = 0; i < sz; i++){
// cout << '>';
// cout << i << endl;
// cout << a.size() << endl;
if(ind[x][st+i]+1 == a.size())continue;
// cout << ' ' ;
// cout << a[i+1] << endl;
if(vis[a[ind[x][st+i]+1]])continue;
rec(a, ind, a[ind[x][st+i]+1], ind[x][st+i]+1, ind[x][st+i+1]-1);
}
}
void create_circuit(int M, vector<int> A) {
ll m = M, n = A.size();
vll a(n); for(ll i = 0; i < n; i++) a[i] = A[i];
vector<vll> ind(m+1); for(ll i = 0; i < n; i++) ind[a[i]].pb(i);
for(ll i = 0; i <= m; i++) ind[i].pb(1e18);
res[0] = a[0];
rec(a, ind, a[0], 0, n);
vector<int> ans(m+1);
for(ll i = 0; i <= m; i++){
// cout << res[i] << endl;
ans[i] = res[i];
}
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;
}
answer(ans, ans_l, ans_r);
}
