#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pill pair<ll, ll>
#define ex exit(0)
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;
const ll N = 8e5 + 100;
ll n;
vector<int> g[N];
ll cur = 0;
ll L[N], R[N];
bool sost[N];
void build(int v, int l, int r) {
if(l == r)
return;
ll m = (l + r) >> 1ll;
if(l != m)
L[v] = cur++, build(L[v], l, m);
if(m + 1 != r)
R[v] = cur++, build(R[v], m + 1, r);
}
void spusk(int v, int p) {
if(sost[v] == 0) {
sost[v] = 1;
if(L[v] == 0) {
L[v] = -(p + 1);
return;
}
else {
spusk(L[v], p);
}
}
else {
sost[v] = 0;
if(R[v] == 0) {
R[v] = -(p + 1);
return;
}
else {
spusk(R[v], p);
}
}
}
void create_circuit(int m, vector<int> a) {
n = a.size();
vector<int> C(m + 1), X, Y;
C[0] = a[0];
for(int i = 1; i < n; i++) {
g[a[i - 1]].pb(a[i]);
}
g[a[n - 1]].pb(0);
for(int i = 1; i <= m; i++) {
if(!g[i].size())
continue;
if(g[i].size() == 1) {
C[i] = g[i][0];
continue;
}
ll zzz = __lg(g[i].size() - 1) + 1;
ll ppp = (1<<zzz) - g[i].size();
ll rt = cur;
C[i] = -(cur + 1);
build(cur++, 1, (1<<zzz));
while(ppp--)
spusk(rt, -rt - 1);
for(auto u : g[i])
spusk(rt, u);
}
for(int i = 0; i < cur; i++) {
X.pb(-(L[i] + 1));
Y.pb(-(R[i] + 1));
}
/* for(auto u : C)
cout << u << " ";
cout << '\n';
for(int i = 0; i < cur; i++)
cout << X[i] << " " << Y[i] << '\n';*/
answer(C, X, Y);
}
/*
int main() {
ll k, kk;
cin >> k >> kk;
vector<int> p;
for(int i = 0, a; i < kk; i++)
cin >> a, p.pb(a);
create_circuit(k, p);
} */
