#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
//CODE
vector<int> tab[43000*4];
vector<pair<int,int>> ans;
set<int> st;
set<int> st_;
vector<int> lleft;
vector<int> rright;
int lst;
void daq(int pos,int l,int r){
/*cout <<pos<<" "<<l<<" "<<r<<endl;
for (int i = 0; i < tab[pos].size(); ++i)
{
cout << tab[pos][i]<<" ";
}cout <<endl;*/
if(l>r) return;
if(l==r){
//if(st_.count(l)) lst=Query(l);
ans.push_back({lleft[l],tab[pos].back()});
return;
}
int mid=(r+l)/2;
int i=r;
while(i>mid){
lst=Query(lleft[i]);
st_.erase(lleft[i]);
i--;
}
if(st.count(tab[pos][0])){
for(auto u:tab[pos]){
int a=Query(u);
//cout << "hey"<< " "<<" "<<u<<" "<<l<<" "<<r<<endl;
st.erase(u);
if (a<lst) tab[pos*2+2].push_back(u);
else tab[pos*2+1].push_back(u);
lst=a;
}
daq(pos*2+1,l,mid);
while(i<=r){
lst=Query(lleft[i]);
st_.insert(lleft[i]);
i++;
}
daq(pos*2+2,mid+1,r);
}else{
for(auto u:tab[pos]){
int a=Query(u);
st.insert(u);
//cout <<"hey"<<" "<<u<<" "<< a <<" "<<lst<<endl;
if (a>lst) tab[pos*2+2].push_back(u);
else tab[pos*2+1].push_back(u);
lst=a;
}
daq(pos*2+1,l,mid);
while(i<=r){
lst=Query(lleft[i]);
st_.insert(lleft[i]);
i++;
}
daq(pos*2+2,mid+1,r);
}
return;
}
void Solve(int N) {
lleft.push_back(0);
rright.push_back(0);
lst=0;
for (int i = 1; i <= 2*N; ++i)
{
int a=Query(i);
if(a>lst) lleft.push_back(i);
else rright.push_back(i);
lst=a;
}
for (int i = 1; i <= N; ++i)
{
tab[0].push_back(rright[i]);
st.insert(rright[i]);
}
daq(0,1,N);
for (int i = 0; i < ans.size(); ++i)
{
Answer(ans[i].first,ans[i].second);
}
}
