#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 100010;
// map<ll, int> v;
mt19937 mt_rand(time(NULL));
int cval;
const int magic = 2;
void go(vector<int>& a, vector<int>& b, bool aactive) {
// cout << "as: ";
// for (int vv : a) cout << vv << " ";
// cout << endl;
// cout << "bs: ";
// for (int vv : b) cout << vv << " ";
// cout << endl;
if (a.size() == 2) {
if (a[0] > b[0] || a[1] > b[1]) {
Answer(a[0], b[1]);
Answer(a[1], b[0]);
return;
}
if (a[0] > b[1] || a[1] > b[0]) {
Answer(a[0], b[0]);
Answer(a[1], b[1]);
return;
}
cval = Query(a[0]);
int cur = Query(b[0]);
if (aactive) {
if (cval == cur) {
Answer(a[0], b[1]);
Answer(a[1], b[0]);
}
else {
Answer(a[0], b[0]);
Answer(a[1], b[1]);
}
}
else {
if (cval == cur) {
Answer(a[0], b[0]);
Answer(a[1], b[1]);
}
else {
Answer(a[0], b[1]);
Answer(a[1], b[0]);
}
}
cval = cur;
return;
}
vector<int> al, bl, ar, br;
shuffle(a.begin(), a.end(), mt_rand);
shuffle(b.begin(), b.end(), mt_rand);
if (a.size() == 1 && b.size() == 1) {
Answer(a[0], b[0]);
return;
}
if (a.size() == 0) return;
int mid = a.size()/2;
for (int i = 0; i < magic; i++) {
if (mid == 1) break;
--mid;
}
//modify what is true for all less than this
for (int i = 0; i < mid; i++) {
cval = Query(a[i]);
al.push_back(a[i]);
}
for (int i = mid; i < a.size(); i++) {
ar.push_back(a[i]);
}
for (int i = 0; i < b.size(); i++) {
// cout << "here: " << b[i] << endl;
if (bl.size() == al.size()) {
br.push_back(b[i]);
continue;
}
if (br.size() == ar.size()) {
bl.push_back(b[i]);
continue;
}
int cur = Query(b[i]);
if (cur != cval) {
if (aactive) {
bl.push_back(b[i]);
}
else {
br.push_back(b[i]);
}
}
else {
if (aactive) {
br.push_back(b[i]);
}
else {
bl.push_back(b[i]);
}
}
cval = cur;
}
go(al, bl, !aactive);
go(ar, br, aactive);
}
void Solve(int N) {
// int nrounds = 1000000/N;
vector<int> cl, cr;
cval = 0;
vector<int> stuff;
for (int i = 1; i <= 2*N; i++) {
stuff.push_back(i);
}
shuffle(stuff.begin(), stuff.end(), mt_rand);
//the above process saves about 2 queries (not worth)
//beginning has more limitations we are not considering
for (int i = 1; i <= 2*N; i++) {
if (cl.size() == N) {
cr.push_back(i);
// mbig[i] = i-1;
continue;
}
int cur = Query(i);
if (cur != cval) {
cl.push_back(i);
}
else cr.push_back(i);
cval = cur;
}
go(cl, cr, true);
}
