#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int>pii;
vector<int> A,B;
int flip(int a, int b){
int res;
for(int i=a; i<=b; i++) res = Query(A[i]);
return res;
}
void Solve(int N) {
int n = N;
vector<pii>v;
v.pb({0,n-1});
vector<int>res[2*n+1];
A.pb(1);
int Prev = Query(1);
for(int i=2; i<=2*n; i++){
int cur = Query(i);
if(cur == Prev) B.pb(i);
else A.pb(i);
Prev = cur;
}
while(v.size()){
int prev;
vector<pii> nv;
for(int x=0; x<v.size(); x++){
auto[a,b] = v[x];
if(a==b) continue;
int m = (a+b)/2;
if(x%2) prev = flip(a,m);
else prev = flip(m+1,b);
nv.pb({a,m});
nv.pb({m+1,b});
}
for(int i=0; i<n; i++){
int cur = Query(B[i]);
if(cur == prev) res[B[i]].pb(1);
else res[B[i]].pb(0);
prev = cur;
}
v = nv;
}
for(int i=0; i<n; i++){
int s=0, e=n-1;
for(auto j: res[B[i]]){
int m = (s+e)/2;
if(j) e=m;
else s=m+1;
if(s==e) break;
}
Answer(B[i],A[s]);
}
}
