#include "minerals.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
#define NDEBUG
using namespace std;
namespace Solver {
const int INF = 1e9;
int curCnt;
vector<int> bestSplit, cost;
vector<bool> inside;
bool ask(int x) // -> return if paired is inside
{
inside[x] = !inside[x];
int diff = Query(x) - curCnt;
curCnt += diff;
// cerr << "ask " << x << ": " << (diff != 0) << ' ' << curCnt << ' ' << inside[x] << endl;
return diff == 0;
}
void solve(vector<int> lef, vector<int> rig)
{
// cerr << "sol [ ";
// for (int x : lef) cerr << x << ' ';
// cerr << "] [ ";
// for (int x : rig) cerr << x << ' ';
// cerr << "]" << endl;
// last of "rig" is always different from the rest of "rig"
int N = (int) lef.size();
if (N == 0) return;
if (N == 1) return Answer(lef[0], rig[0]);
if (N == 2) {
assert(inside[rig[0]] != inside[rig[1]]);
if (ask(lef[0]) != inside[rig[0]]) swap(lef[0], lef[1]);
return Answer(lef[0], rig[0]), Answer(lef[1], rig[1]);
}
if (N == 3) {
if (ask(lef[0]) == inside[rig.back()]) {
Answer(lef[0], rig.back());
lef.erase(lef.begin());
rig.erase(prev(rig.end()));
ask(rig.back());
return solve(lef, rig);
}
if (ask(lef[1]) == inside[rig.back()]) {
Answer(lef[1], rig.back());
lef.erase(lef.begin() + 1);
rig.erase(prev(rig.end()));
swap(lef[0], lef[1]);
return solve(rig, lef);
}
Answer(lef.back(), rig.back());
lef.erase(prev(lef.end()));
rig.erase(prev(rig.end()));
ask(rig.back());
return solve(lef, rig);
}
int split = bestSplit[N];
for (int i = N - split; i < N - 1; ++i) ask(rig[i]);
vector<int> lef1, lef2;
lef1.reserve(N - split), lef2.reserve(split);
for (int i = 0; i < N - 1; ++i) {
if (ask(lef[i]) == inside[rig[0]]) lef1.push_back(lef[i]);
else lef2.push_back(lef[i]);
}
if ((int) lef1.size() < N - split) {
lef1.push_back(lef.back());
ask(lef2.back());
} else {
lef2.push_back(lef.back());
ask(lef1.back());
}
vector<int> rig1(rig.begin(), rig.end() - split), rig2(rig.end() - split, rig.end());
solve(rig1, lef1);
solve(rig2, lef2);
}
void run(int N)
{
curCnt = 0;
cost.assign(N + 1, INF);
bestSplit.resize(N + 1);
inside.assign(N * 2 + 1, false);
cost[0] = 0, cost[1] = 0, cost[2] = 1, cost[3] = 3, bestSplit[3] = 1;
for (int i = 4; i <= N; ++i) {
for (int &x = (bestSplit[i] = bestSplit[i - 1]); x + 1 < i && i + x + cost[x] + cost[i - x] > i + x + 1 + cost[x + 1] + cost[i - x - 1]; ++x);
cost[i] = i + bestSplit[i] + cost[bestSplit[i]] + cost[i - bestSplit[i]] - 1;
}
// cerr << cost[N] + 2 * N << endl;
vector<int> lef, rig;
for (int i = 1; i < 2 * N; ++i) {
if (ask(i)) lef.push_back(i);
else rig.push_back(i);
}
if (lef.size() < rig.size()) lef.swap(rig);
rig.push_back(2 * N);
solve(lef, rig);
}
}
void Solve(int N)
{ Solver::run(N); }
