#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;
void Solve(int n) {
n<<=1;
mt19937 rnd(time(NULL));
vector<int> p;
vector<int> gr(n);
vector<ii> qu(n);
vector<vector<int>> ask(n);
vector<int> A,B;
for(int i=1;i<=n;i++) p.pb(i);
shuffle(p.begin(),p.end(),rnd);
int cnt=0;
for(int i=0;i<n;i++) {
int cur=Query(p[i]);
if(cur>cnt) {
gr[i]=0;
A.pb(i);
}
else {
gr[i]=1;
qu[i]={0,sz(A)-1};
if(qu[i].st!=qu[i].nd) ask[(qu[i].st+qu[i].nd)>>1].pb(i);
B.pb(i);
}
cnt=cur;
}
// values in vectors are just indices not permuation values
int last=sz(A)-1;
while(1) {
bool flag2=1;
for(int t=1;t<=2;t++) {
int has=0;
for(int i=0;i<sz(A);i++) has+=sz(ask[i]);
if(!has) {
flag2=0;
break ;
}
if(t==1) {
for(int i=last;i>=0;i--) {
for(auto x:ask[i]) {
int cur=Query(p[x]);
if(cur!=cnt) {
qu[x].st=i+1;
}
else {
qu[x].nd=i;
}
cnt=cur;
if(qu[x].st!=qu[x].nd) {
int mid=(qu[x].st+qu[x].nd)>>1;
if(mid>i) --has;
ask[mid].pb(x);
}
}
ask[i].clear();
if(!has) break ;
last=i;
cnt=Query(p[A[i]]);
}
}
else {
for(int i=last;i<sz(A);i++) {
cnt=Query(p[A[i]]);
for(auto x:ask[i]) {
int cur=Query(p[x]);
if(cur!=cnt) {
qu[x].st=i+1;
}
else {
qu[x].nd=i;
}
cnt=cur;
if(qu[x].st!=qu[x].nd) {
int mid=(qu[x].st+qu[x].nd)>>1;
if(mid<i) --has;
ask[mid].pb(x);
}
}
ask[i].clear();
if(!has) break ;
last=i;
}
}
}
if(!flag2) break ;
}
for(int i:B) {
int pos=qu[i].st;
Answer(p[A[pos]],p[i]);
}
}
