#include "minerals.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
using vi = vector<int>;
const int maxN = 43'000;
int N;
vi mushroom(1+2*maxN, 0);
int last_ans = 0;
int sz(vi& x)
{
return int(x.size());
}
void dnc(vi L, vi R, bool bL, bool bR)
{
// cerr << "dnc " << b << " : ";
// for(int l:L) cerr << l << ' ';
// cerr << " | ";
// for(int r:R) cerr << r << ' ';
// cerr << "\n";
if(int(L.size()) == 1)
Answer(L[0], R[0]);
else if(int(L.size()) == 2)
{
if(!bL) last_ans = Query(L[0]);
else last_ans = Query(L[1]); //0 is active
int prev_ans = last_ans;
last_ans = Query(R[0]);
if(prev_ans == last_ans)
{
Answer(L[0], R[0]);
Answer(L[1], R[1]);
}
else
{
Answer(L[0], R[1]);
Answer(L[1], R[0]);
}
}
else
{
int K = int(L.size());
vi L1, L2;
for(int i = 0; i < K/2; i++)
L1.push_back(L[i]);
for(int i = K/2; i < K; i++)
L2.push_back(L[i]);
if(bL)
{
for(int l: L2)
last_ans = Query(l);
}
else
{
for(int l: L1)
last_ans = Query(l);
}
vi R1, R2;
for(int r:R)
{
if(sz(R1) == sz(L1) && sz(R2) + 1 == sz(L2))
{
R2.push_back(r);
}
else if(sz(R1) + 1 == sz(L1) && sz(R2) == sz(L2))
{
R1.push_back(r);
}
else
{
int prev_ans = last_ans;
last_ans = Query(r);
if(last_ans == prev_ans)
{
R1.push_back(r);
}
else
{
R2.push_back(r);
}
}
}
dnc(L1, R1, 1, !bR);
dnc(L2, R2, 0, !bR);
}
}
void Solve(int N_)
{
N = N_;
int ct = 0;
for(int i = 1; i <= 2*N; i++)
{
last_ans = Query(i);
if(last_ans > ct)
{
// cerr << "increasing ct = " << ct << " at " << i << '\n';
ct++;
mushroom[i] = ct;
// cerr << i << " : " << mushroom[i] << '\n';
}
}
// cerr << "check\n";
// for(int i = 1; i <= 2*N; i++) cerr << i << " : " << mushroom[i] << '\n';
vi leftval, rightval;
for(int i = 1; i <= 2*N; i++)
{
if(mushroom[i])
leftval.push_back(i);
else
rightval.push_back(i);
}
dnc(leftval, rightval, 1, 1);
}
