#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, aa[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(aa[*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(aa[*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(aa[*it2]);
if(don < onc)
a.insert(*it2);
onc = don;
}
Query(aa[*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++){
aa[i] = i;
s.insert(i);
}
random_shuffle(aa + 1, aa + n + 1, myrandom);
// for(int i = 1; i <= n; i++)
// cout << aa[i] << " ";cout << endl;
coz(s, n/2);
return;
}
