#include "minerals.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 1000005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
typedef set < int > si;
int n, top = 1, a[MAXN], u[MAXN];
si s;
si :: iterator it, it2;
int myrandom(int x){
return rand()%x;
}
void coz(si s, int x){
if((int)s.size() == 2){
vector < int > x;
for(it = s.begin(); it != s.end(); it++)
x.pb(*it);
Answer(x[0], x[1]);
return;
}
si a;
int top = 0, onc = 0, don;
for(it = s.begin(); it != s.end(); it++){
top++;
don = top - Query(*it);
// cout << *it << " " << don << endl;
if(don > onc)
a.insert(*it);
onc = don;
if(don >= x/2){
// cout << "Burda BOL" << endl;
for(it2 = s.begin(); it2 != it; it2++){
top--;
don = top - Query(*it2);
if(don < onc)
a.insert(*it2);
onc = don;
}
Query(*it);
break;
}
}
for(it = a.begin(); it != a.end(); it++){
// cout << *it << endl;
s.erase(*it);
}
coz(a, x/2);
coz(s, x - x/2);
}
void Solve(int n) {n*= 2;
srand(time(0));
::n = n;
for(int i = 1; i <= n; i++){
a[i] = i;
s.insert(i);
}
coz(s, n/2);
return;
// random_shuffle(a + 1, a + n + 1, myrandom);
// for(int i = 1; i <= n; i++)
// cout << a[i] << " ";cout << endl;
// n *= 2;
for(int i = 1; i <= n; i++){
top++;
int don = top - Query(a[i]);
cout << i << " " << don << endl;
if(don == 2 and 0){
for(int j = 1; j < i; j++){
if(u[a[j]])
continue;
top--;
int don = top - Query(a[j]);
// cout << j << " " << don << endl;
if(don == 1){
for(int k = j - 1; k >= 1; k--)
if(!u[a[k]]){
top++;
Query(a[k]);
}
u[a[j]] = u[a[i]] = 1;
// cout << "Buldum " << i << " " << j << endl;
Answer(a[i], a[j]);
top--;
Query(a[i]);
break;
}
}
// cout << "Bitti" << endl;
}
}
}
