#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});
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;
}
pii res[2*n+1];
for(int i=0; i<n; i++) res[B[i]] = {0,n-1};
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++){
auto[s,e] = res[B[i]];
int m = (s+e)/2;
if(s == e) continue;
int cur = Query(B[i]);
if(cur == prev) res[B[i]] = {s,m};
else res[B[i]] = {m+1,e};
prev = cur;
}
v = nv;
}
for(int i=0; i<n; i++) {
auto[s,e] = res[B[i]];
Answer(B[i], A[res[B[i]].first]);
}
}
