#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) ((int)v.size())
#define forn(i,n) for(int i = 0; i < n; ++i)
#define forbe(i,b,e) for(int i = b; i < e; ++i)
#define pb push_back
#define pry puts("YES")
#define prn puts("NO")
#define endl '\n'
#define fst first
#define scn second
const int N = 2e5;
const int M = 1e5;
vector<int> etrig[M+1];
vector<int> X;
vector<int> Y;
int cnt = 1;
int
dfs(int x, int s, int k)
{
if ((sz(etrig[x])-s-1)/(1<<k) == 0) return etrig[x][s];
int size = 1 + (sz(etrig[x])-s-1)/(1<<k);
if (size&1)
assert(0);
int _y = dfs(x,s+(1<<k),k+1);
int _x = dfs(x,s,k+1);
if (_x == _y)
return _x;
X.pb(0);
Y.pb(0);
Y[cnt-1] = _y;
X[cnt-1] = _x;
++cnt;
return -(cnt-1);
}
int
donode(int x)
{
int scount = cnt++;
X.pb(0);
Y.pb(0);
int last = 0;
for (int j = 0; j < 20; ++j) {
if (sz(etrig[x])&(1<<j))
last = j;
}
if (sz(etrig[x]) != (1<<last))
++last;
if (sz(etrig[x]) < (1<<last)) {
X.pb(0);
Y.pb(0);
X[cnt-1] = -cnt;
Y[cnt-1] = -scount;
while (sz(etrig[x]) < (1<<last))
etrig[x].pb(-cnt);
++cnt;
}
X[scount-1] = dfs(x,0,1);
Y[scount-1] = dfs(x,1,1);
return - scount;
}
void answer(vector<int> c, vector<int> X, vector<int> Y);
void
create_circuit(int m, vector<int> a)
{
int n = sz(a);
vector<int> trigexit(m+1);
for (int i = 0; i < n-1; ++i) {
etrig[a[i]].pb(a[i+1]);
assert(a[i] != 0);
}
etrig[a[n-1]].pb(0);
trigexit[0] = a[0];
for (int i = 1; i <= m; ++i) {
if (sz(etrig[i]) == 0) {
trigexit[i] = 0;
} else if (sz(etrig[i]) == 1) {
trigexit[i] = etrig[i][0];
} else {
trigexit[i] = donode(i);
}
}
answer(trigexit,X,Y);
return;
}
#ifdef ONPC
void
answer(vector<int> c, vector<int> X, vector<int> Y)
{
for (int i = 0; i < sz(c); ++i) {
cout << i << ": " << c[i] << endl;
}
for (int i = 0; i < sz(X); ++i) {
cout << i+1 << ": " << X[i] << endl;
cout << i+1 << ": " << Y[i] << endl;
}
}
void
solve()
{
int m = 10;
vector<int> c = {1, 2, 10, 1, 3, 1, 4, 1, 5, 1, 6,1, 7};
create_circuit(m,c);
}
int32_t
main()
{
freopen("in", "r", stdin);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
