#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;
void make(int l,int mid,int r) {
for(int i=l;i<=mid;i++) {
if(!on[i]) cnt=Query(p[A[i]]),on[i]=!on[i];
}
for(int i=mid+1;i<=r;i++) {
if(on[i]) 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;
make(l,mid,r);
vector<int> lcd,rcd;
bool tol=0,tor=0;
shuffle(cd.begin(),cd.end(),rnd);
for(auto x:cd) {
if(tol) {lcd.pb(x);continue ;}
if(tor) {rcd.pb(x);continue ;}
int cur=Query(p[x]);
if(cnt!=cur) {
rcd.pb(x);
}
else {
lcd.pb(x);
}
cnt=cur;
if(sz(lcd)==mid-l+1) tor=1;
if(sz(rcd)==r-mid) tol=1;
}
solve(l,mid,lcd);
solve(mid+1,r,rcd);
}
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);
}
