#include "minerals.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5;
int mk[N];
int la = 0;
bool Ask(int u){
mk[u] ^= 1;
int res = Query(u);
bool ch = la != res;
la = res;
return ch;
}
int norm(vector<int>& A){
int c0 = 0;
int c1 = 0;
int n = A.size();
for(auto x : A)
(mk[x] ? c1 : c0) ++;
return (n / 2) - min(c0, c1);
}
void normalize(vector<int>& A){
int c0 = 0;
int c1 = 0;
int n = A.size();
for(auto x : A)
(mk[x] ? c1 : c0) ++;
int mn = 0, cnt = c0;
if(c0 > c1) mn = 1, cnt = c1;
for(auto x : A){
if(cnt == (n / 2)) break;
if(mn == mk[x]) continue;
cnt ++;
Ask(x);
}
}
void solve(vector<int> A, vector<int> B){
assert(A.size() == B.size());
// random_shuffle(A.begin(), A.end());
// random_shuffle(B.begin(), B.end());
int n = A.size();
if(n == 1){
Answer(A[0], B[0]);
return ;
}
if(norm(A) > norm(B)) swap(A, B);
normalize(A);
sort(A.begin(), A.end(), [&](int i, int j){
return mk[i] > mk[j];
});
int sz = 0;
for(auto x : A) if(mk[x]) sz ++;
vector<int> A2[2], B2[2];
for(int i = 0; i < sz; i++) A2[0].pb(A[i]);
for(int i = sz; i < n; i++) A2[1].pb(A[i]);
for(auto x : B){
if(A2[0].size() == B2[0].size()){
B2[1].pb(x);
continue;
}
if(A2[1].size() == B2[1].size()){
B2[0].pb(x);
continue;
}
bool fl = Ask(x);
B2[fl ? 1 : 0].pb(x);
}
solve(A2[0], B2[0]);
solve(A2[1], B2[1]);
}
void Solve(int n) {
vector<int> A, B;
for(int i = 1; i <= n + n; i++)
if(Ask(i))
A.pb(i);
else
B.pb(i);
solve(A, B);
}
