#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
vector<int> Q;
vector<int> P;
int ans[86005];
int ON[86005];
int last;
int query(int x){
ON[x] ^= 1;
return Query(x);
}
void solve(vector<int> p, int l, int r, int flag){
if (r == l){
Answer(Q[l],p[0]);
return;
}
else if (l + 1 == r){
//printf("last query %d\n",last);
int q1;
if (flag) q1 = query(Q[r]);
else q1 = query(Q[l]);
assert(ON[Q[l]] && !ON[Q[r]]);
if (ON[p[0]] ^ ON[p[1]]){
//printf("-----------------------------------------TWO\n");
//printf("%d %d <-> %d %d\n",Q[l],Q[r],p[0],p[1]);
//printf("flag = %d, q1 = %d, last = %d\n",flag,q1,last);
int On = ON[p[0]]?0:1;
int Off = 1^On;
On = p[On], Off = p[Off];
if ((q1 == last) ^ flag){
Answer(Q[l],On);
Answer(Q[r],Off);
}
else{
Answer(Q[l],Off);
Answer(Q[r],On);
}
last = q1;
return;
}
last = q1;
q1 = query(p[0]);
if ((q1 == last)) ans[Q[l]] = p[0], ans[Q[r]] = p[1];
else ans[Q[l]] = p[1], ans[Q[r]] = p[0];
Answer(Q[l],ans[Q[l]]);
Answer(Q[r],ans[Q[r]]);
last = q1;
return;
}
#ifdef debug
printf("new <%d,%d> %d\n",l,r,flag);
for (auto x : p){
printf("%d ",x);
}
printf("<- P\n");
for (int i = l; i <= r; i++){
printf("%d ",Q[i]);
}
printf("<- Q\n");
#endif
//assert(p.size() == r-l+1);
vector<int> Lp;
vector<int> Rp;
int n = r-l+1;
int mid;
mid = (l+r)/2;
if (flag){
for (int i = mid+1; i <= r; i++){
last = query(Q[i]);
}
}
else{
for (int i = l; i <= mid; i++){
last = query(Q[i]);
}
}
for (int i = 0; i < n; i++){
int q = query(p[i]);
if (q == last){
Lp.push_back(p[i]);
}
else{
Rp.push_back(p[i]);
}
last = q;
if (Lp.size() == mid-l+1 || Rp.size() == r-mid){
//printf("ALL FILLED\n");
for (int j = i+1; j < n; j++){
if (Lp.size() == mid-l+1) Rp.push_back(p[j]);
else Lp.push_back(p[j]);
}
break;
}
}
#ifdef debug
printf("Lp: ");
for (auto x : Lp) printf("%d ",x);
printf("\n");
printf("Rp: ");
for (auto x : Rp) printf("%d ",x);
printf("\n");
#endif
solve(Lp, l, mid, 1);
solve(Rp, mid+1, r, 0);
}
void Solve(int N) {
int last = 0;
for (int i = 1; i <= 2*N; i++){
int q = query(i);
if (q == last){
Q.push_back(i);
}
else{
P.push_back(i);
}
last = q;
ON[i] = 1;
}
srand(time(NULL));
random_shuffle(Q.begin(),Q.end());
random_shuffle(P.begin(),P.end());
solve(P,0,N-1,1);
}
