#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
int kl;
void slv(vector<int> v1, vector<int> v2) {
/*for(auto i : v1) cout << i << " ";
cout << "\n";
for(auto i : v2) cout << i << " ";
cout << "\n" << "\n";*/
if((int)v1.size() == 1) {
Answer(v1[0], v2[0]);
return;
}
int n = (int)v1.size();
vector<int> l1, l2, r1, r2;
for(int i = 0; i < n / 2; i++) l1.push_back(v1[i]);
for(int i = n / 2; i < n; i++) r1.push_back(v1[i]);
map<int, int> mp;
shuffle(v2.begin(), v2.end(), rng);
for(int i = 0; i < n; i++) {
if(l2.size() == l1.size()) {
r2.push_back(v2[i]);
continue;
}
if(r2.size() == r1.size()) {
l2.push_back(v2[i]);
continue;
}
int k = Query(v2[i]);
//cout << k << " " << kl << " " << v2[i] << " f\n";
if(k == kl) l2.push_back(v2[i]), mp[v2[i]] = 1;
else r2.push_back(v2[i]), mp[v2[i]] = 2;
kl = k;
}
int S1 = (int)l1.size();
if(n / 2 > 1) {
for(int i = S1 / 2; i < S1; i++) kl = Query(l1[i]);
for(auto i : v2) if(mp[i] == 1) kl = Query(i);
}
slv(l1, l2);
swap(r1, r2);
if(n - n / 2 > 1) {
int S = (int)r1.size();
for(int i = 0; i < S / 2; i++) if(!mp[r1[i]]) kl = Query(r1[i]);
for(int i = S / 2; i < S; i++) if(mp[r1[i]]) kl = Query(r1[i]);
}
slv(r1, r2);
}
void Solve(int n) {
vector<int> v1, v2;
map<int, int> mp;
kl = 0;
for(int i = 1; i <= 2 * n; i++) {
if(kl == n) {
v2.push_back(i);
continue;
}
int k = Query(i);
mp[i] = 1;
if(k == kl) v2.push_back(i);
else v1.push_back(i);
kl = k;
}
for(int i = 0; i < n / 2; i++) if(!mp[v1[i]]) kl = Query(v1[i]);
for(int i = n / 2; i < n; i++) if(mp[v1[i]]) kl = Query(v1[i]);
for(auto i : v2) if(mp[i]) kl = Query(i);
slv(v1, v2);
}
