#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int MAXN = 1e5+1;
bool on[MAXN];
int current;
int query(int x) {
on[x] = !on[x];
current = Query(x);
return current;
}
int levels = 0;
void solve(int n, vi ls, vi rs) {
if(n==1) {
Answer(ls[0], rs[0]);
return;
}
random_shuffle(ls.begin(), ls.end());
random_shuffle(rs.begin(), rs.end());
vi Ls[2], Rs[2];
int mid = max(1, n/3);
for(int i=0; i<mid; ++i) {
query(ls[i]);
Ls[on[ls[i]]].push_back(ls[i]);
}
for(int i=mid; i<n; ++i) {
Ls[on[ls[i]]].push_back(ls[i]);
}
for(int i=0; i<n; ++i) {
int old = current;
if(Rs[0].size() == Ls[0].size()) {
current = old;
}
else if(Rs[1].size() == Ls[1].size()) {
current--;
}
else {
query(rs[i]);
}
if(current == old) {
Rs[1].push_back(rs[i]);
}
else {
Rs[0].push_back(rs[i]);
}
}
assert(Ls[0].size() == Rs[0].size() && Ls[1].size() == Rs[1].size());
solve(Ls[0].size(), Ls[0], Rs[0]);
solve(Ls[1].size(), Ls[1], Rs[1]);
}
void Solve(int N) {
vi ls={}, rs={};
int val = 0;
vi order;
for(int i=1; i<=2*N; ++i) {
order.push_back(i);
}
random_shuffle(order.begin(), order.end());
for(int i: order) {
int nval = query(i);
if(nval == val) {
rs.push_back(i);
}
else {
ls.push_back(i);
}
val = nval;
}
solve(N, ls, rs);
}
