#include "doll.h"
#include <bits/stdc++.h>
#define deb(x) cout << #x << " ---> " << x << endl
using namespace std;
// void answer(vector <int> C, vector <int> X, vector <int> Y) {
// cout << C.size() << endl;
// for (auto x:C) {
// cout << x << " " ;
// }
// cout << endl;
// cout << X.size() << endl;
// for (int i = 0; i < X.size(); i++) {
// cout << X[i] << " " << Y[i] << endl;
// }
// }
vector <vector<int>> v(1e6+5);
vector <vector<pair<int,int>>> D(1e6+5);
void dfs(int x, int num,int lim, int d) {
// deb(x);
D[(1<<d)].push_back({x,num});
int lx = x*2;
int lnum = num;
if (lx <= lim) {
dfs(lx, lnum, lim, d+1);
}
int rx = x*2+1;
int rnum = num + (1<<d);
if (rx <= lim) {
dfs(rx,rnum,lim,d+1);
}
}
void create_circuit(int M, vector<int> A) {
dfs(1,0,4*M,0);
for (int i = 1; (1<<i) <= M; i++) {
sort(D[(1<<i)].begin(),D[(1<<i)].end());
}
// for (int i = 0; (1<<i) <= M; i++) {
// cout << i << "<---->" << endl;
// for (auto [x,ord]:D[(1<<i)]) {
// cout << ord << " ";
// }
// cout << endl;
// }
A.push_back(0);
int N = A.size();
vector<int> C(M + 1);
for (int i = 0; i <= M; ++i) {
C[i] = -1;
}
vector<int> X, Y;
for (int i = 0; i <= N-1; i++) {
v[0].push_back(A[i]);
}
int S = 1;
// cout << 1 << endl;
for (int i = 0; i <= 0; i++) {
// cout << i << endl;
int k = v[i].size();
if (k == 1) {
C[i] = v[i][0];
} else if (k > 1) {
// cout << i << endl;
int cur = 2;
vector <int> res;
C[i] = (0-S);
res.push_back(S++);
X.push_back(-1);
Y.push_back(-1);
while (cur < k) {
vector <int> nres;
for (auto x:res) {
X[x-1] = (0-S);
Y[x-1] = (0-(S+1));
nres.push_back(S);
nres.push_back(S+1);
X.push_back(-1);
Y.push_back(-1);
X.push_back(-1);
Y.push_back(-1);
S+=2;
}
cur *= 2;
res = nres;
}
vector <int> id(cur);
iota(id.begin(),id.end(),0);
sort(id.begin(),id.end(),[cur](int a, int b) {
return D[cur][a].second < D[cur][b].second;
});
int xr = cur-k;
for (int j = 0; j < xr; j++) {
int ind = id[j];
if (ind%2==0) {
int o = ind/2;
X[res[o]-1] = C[i];
} else {
int o = ind/2;
Y[res[o]-1] = C[i];
}
}
for (int j = xr; j < cur; j++) {
int ind = id[j];
if (ind%2==0) {
int o = ind/2;
X[res[o]-1] = v[i][j-xr];
} else {
int o = ind/2;
Y[res[o]-1] = v[i][j-xr];
}
}
}
}
answer(C, X, Y);
}
// int main () {
// int n,m;
// cin >> m;
// cin >> n;
// vector <int> a(n);
// for (int i= 1; i <= n; i++) {
// cin >> a[i-1];
// }
// create_circuit(m,a);
// }
