#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, cur, ans[100100], chk[100100];
int dp[100100], opt[100100];
void dnc0(vector<int> a);
void dnc1(vector<int> L, vector<int> R, int onL, int onR);
int myquery(int x){
chk[x] ^= 1;
cur = Query(x);
return cur;
}
void dnc0(vector<int> a){
int c = a.size() / 2;
if (c==0) return;
if (c==1){
ans[a[0]] = a[1];
ans[a[1]] = a[0];
return;
}
vector<int> L, R;
for (auto &x:a){
int prv = cur;
int now = myquery(x);
if (now==prv){
R.push_back(x);
}
else{
L.push_back(x);
}
}
dnc1(L, R, 1, 1);
}
void dnc1(vector<int> L, vector<int> R, int onL, int onR){
int c = L.size();
if (c==0) return;
if (c==1){
ans[L[0]] = R[0];
ans[R[0]] = L[0];
return;
}
vector<int> L1, R1, L2, R2;
for (int i=0;i<opt[c];i++) {L1.push_back(L[i]); myquery(L[i]);}
for (int i=opt[c];i<c;i++) L2.push_back(L[i]);
for (auto &x:R){
if (x==R.back()){
if (L1.size()!=R1.size()) R1.push_back(x);
else R2.push_back(x);
break;
}
int prv = cur;
int delta = myquery(x) - prv;
if ((!onL) == (delta==0)) R1.push_back(x);
else R2.push_back(x);
}
dnc1(L1, R1, !onL, !onR);
dnc1(L2, R2, onL, !onR);
}
void run(int MX){
dp[0] = 0;
dp[1] = 0;
for (int i=2;i<=MX;i++){
dp[i] = 1e9;
opt[i] = -1;
int s = 0.27 * i;
int e = 0.4 * i;
if (i<=100) s = 1, e = i-1;
for (int j=s;j<=e;j++){
int val = j + (i-1) + dp[j] + dp[i-j];
if (val < dp[i]) dp[i] = val, opt[i] = j;
}
}
}
void Solve(int N) {
run(43000);
n = N, cur = 0;
vector<int> a;
for (int i=1;i<=n*2;i++) a.push_back(i);
dnc0(a);
for (int i=1;i<=n*2;i++) if (i < ans[i]) Answer(i, ans[i]);
}
