#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
int curr = 0;
bool change(int u){
int nxt = Query(u);
bool res = (nxt != curr);
curr = nxt;
return res;
}
void Solve(int N){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> group[2];
for(int i=1;i<=2*N;i++) group[change(i)].emplace_back(i);
shuffle(group[0].begin(),group[0].end(),rng);
int l[N],r[N];
vector<int> mid[N];
for(int i=0;i<N;i++){
l[i] = 0;
r[i] = N-1;
mid[r[i] - (382*(r[i]-l[i]+1)/1000)].emplace_back(i);
}
// for(auto u : group[0]) cout << u << ' '; cout << '\n';
// for(auto u : group[1]) cout << u << ' '; cout << '\n';
int found = 0;
while(found < N){
// for(int i=0;i<N;i++) cout << l[i] << ' '; cout << '\n';
// for(int i=0;i<N;i++) cout << r[i] << ' '; cout << '\n'; cout << '\n';
int lmin = N, rmax = 0;
for(int i=0;i<N;i++){
lmin = min(lmin,l[i]);
rmax = max(rmax,r[i]);
}
for(int i=rmax;i>=lmin;i--){
change(group[0][i]);
vector<int> curr = mid[i];
mid[i].clear();
for(auto u : curr){
bool nxt = change(group[1][u]);
if(nxt){
l[u] = i;
int nxm = l[u] + (618*(r[u]-l[u]+1)/1000);
if(nxm == r[u]) nxm--;
// cout << "nxm 1 : " << group[0][i] << ' ' << group[1][u] << ' ' << nxm << ' ' << r[u] << ' ' << l[u] << '\n';
if(l[u] == r[u]){
Answer(group[0][l[u]],group[1][u]);
found++;
}else mid[nxm].emplace_back(u);
}else{
r[u] = i-1;
int nxm = r[u] - (382*(r[u]-l[u]+1)/1000);
// cout << "nxm 2 : " << group[0][i] << ' ' << group[1][u] << ' ' << nxm << ' ' << r[u] << ' ' << l[u] << '\n';
if(l[u] == r[u]){
Answer(group[0][l[u]],group[1][u]);
found++;
}else mid[nxm].emplace_back(u);
}
}
}
for(int i=lmin;i<rmax;i++){
change(group[0][i]);
vector<int> curr = mid[i];
mid[i].clear();
for(auto u : curr){
bool nxt = change(group[1][u]);
if(nxt){
l[u] = i+1;
int nxm = l[u] + (382*(r[u]-l[u]+1)/1000);
// cout << "nxm 3 : " << group[0][i] << ' ' << group[1][u] << ' ' << nxm << ' ' << r[u] << ' ' << l[u] << '\n';
if(l[u] == r[u]){
Answer(group[0][l[u]],group[1][u]);
found++;
}else mid[nxm].emplace_back(u);
}else{
r[u] = i;
int nxm = r[u] - (618*(r[u]-l[u]+1)/1000);
if(nxm == l[u]) nxm++;
// cout << "nxm 4 : " << group[0][i] << ' ' << group[1][u] << ' ' << nxm << ' ' << r[u] << ' ' << l[u] << '\n';
if(l[u] == r[u]){
Answer(group[0][l[u]],group[1][u]);
found++;
}else mid[nxm].emplace_back(u);
}
}
}
}
}
