#include "minerals.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 2000000000000000
#define N 500005
#define MOD 998244353
#define KOK 700
using namespace std;
vector<int> A,B;
vector<int> p;
vector<int> on;
int cnt;
mt19937 rnd;
int get(int l,int mid,int r,int ss) {
int tot=0;
for(int i=l;i<=mid;i++) {
if(!(on[i]^ss)) tot++;
}
for(int i=mid+1;i<=r;i++) {
if((on[i]^ss)) tot++;
}
return tot;
}
void make(int l,int mid,int r,int ss) {
for(int i=l;i<=mid;i++) {
if(!(on[i]^ss)) cnt=Query(p[A[i]]),on[i]=!on[i];
}
for(int i=mid+1;i<=r;i++) {
if((on[i]^ss)) cnt=Query(p[A[i]]),on[i]=!on[i];
}
}
void solve(int l,int r,vector<int> cd) {
if(l==r) {
for(auto x:cd) Answer(p[x],p[A[l]]);
return ;
}
int mid=(l+r)>>1;
int sw=0;
int sz[2]={mid-l+1,r-mid};
int tot[2]={0,0};
tot[0]=get(l,mid,r,0);
tot[1]=get(l,mid,r,1);
if(tot[1]<tot[0]) {
make(l,mid,r,1);
sw=1;
swap(sz[0],sz[1]);
} else make(l,mid,r,0);
vector<int> go[2];
bool to[2]={0,0};
shuffle(cd.begin(),cd.end(),rnd);
for(auto x:cd) {
if(to[0]) {go[0].pb(x);continue ;}
if(to[1]) {go[1].pb(x);continue ;}
int cur=Query(p[x]);
if(cnt!=cur) {
go[1].pb(x);
}
else {
go[0].pb(x);
}
cnt=cur;
if(sz(go[0])==sz[0]) to[1]=1;
if(sz(go[1])==sz[1]) to[0]=1;
}
if(sw) swap(go[0],go[1]);
solve(l,mid,go[0]);
solve(mid+1,r,go[1]);
}
void Solve(int n) {
n<<=1;
rnd=mt19937(time(NULL));
on=vector<int>(n,0);
for(int i=1;i<=n;i++) p.pb(i);
shuffle(p.begin(),p.end(),rnd);
bool toA=0,toB=0;
for(int i=0;i<n;i++) {
if(toA) {A.pb(i);continue ;}
if(toB) {B.pb(i);continue ;}
int cur=Query(p[i]);
on[i]=!on[i];
if(cur>cnt) {
A.pb(i);
}
else {
B.pb(i);
}
if(sz(A)==n/2) toB=1;
if(sz(B)==n/2) toA=1;
cnt=cur;
}
solve(0,sz(A)-1,B);
}
