#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
const int MAXN = 43002;
int isoff[MAXN];
int rozw(vector<int> lewo, vector<int> prawo, bool c, int prev){
if(lewo.size() == 0 and prawo.size() == 0) return prev;
if(lewo.size() == 1 and prawo.size() == 1) { Answer(lewo[0], prawo[0]); return prev; }
// if(lewo.size() == 2 and prawo.size() == 2){
// if(c){
// int curr = Query(lewo[0]);
// int nowy = Query(prawo[0]);
// if(nowy != curr){
// Answer(lewo[0], prawo[0]);
// Answer(lewo[1], prawo[1]);
// return;
// }
// else{
// Answer(lewo[0], prawo[1]);
// Answer(lewo[1], prawo[0]);
// return;
// }
// }
// else{
// int curr = Query(lewo[0]);
// int nowy = Query(prawo[0]);
// if(nowy == curr){
// Answer(lewo[0], prawo[0]);
// Answer(lewo[1], prawo[1]);
// return;
// }
// else{
// Answer(lewo[0], prawo[1]);
// Answer(lewo[1], prawo[0]);
// return;
// }
// }
// }
// cerr << lewo.size() << " " << prawo.size() << " " << c << " " << prev << "\n";
// for(auto u : lewo){
// cerr << u << " ";
// }
// cout << " lew\n";
// for(auto u : prawo){
// cerr << u << " ";
// }
// cerr << " praw\n";
int mid = lewo.size() / 2;
vector<int> l1;
vector<int> l2;
vector<int> p1;
vector<int> p2;
int curr = prev;
for(int i = 0; i < prawo.size(); ++i){
if(isoff[prawo[i]] == c ^ 1 and l1.size() < mid){
l1.push_back(prawo[i]);
}
else if(isoff[prawo[i]] == c and l2.size() < mid){
l2.push_back(prawo[i]);
}
else{
isoff[prawo[i]] ^= 1;
curr = Query(prawo[i]);
(l1.size() < l2.size() ? l1.push_back(prawo[i]) : l2.push_back(prawo[i]));
}
}
for(int i = 0; i < lewo.size(); ++i){
if(c == true){
int nowy = Query(lewo[i]);
isoff[lewo[i]] ^= 1;
if(nowy == curr){
p2.push_back(lewo[i]);
}
else{
p1.push_back(lewo[i]);
}
curr = nowy;
}
else{
int nowy = Query(lewo[i]);
isoff[lewo[i]] ^= 1;
if(nowy != curr){
p2.push_back(lewo[i]);
}
else{
p1.push_back(lewo[i]);
}
curr = nowy;
}
}
int w = rozw(l1, p1, c ^ 1, curr);
w = rozw(l2, p2, c, w);
return w;
}
void Solve(int N){
vector<int> lewo;
vector<int> prawo;
int prev = 0;
for(int i = 1; i <= 2 * N; ++i){
if(lewo.size() == N){
prawo.push_back(i);
continue;
}
int ile = Query(i);
isoff[i] ^= 1;
if(ile != prev){
lewo.push_back(i);
}
else{
prawo.push_back(i);
}
prev = ile;
}
rozw(lewo, prawo, 1, N);
return;
}
