#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 45000;
int dp[maxn], opt[maxn];
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
struct RNG {
int operator () (int n) {
return rnd(n);
}
};
int cnt = 0;
void solve(vector<int> u, vector<int> v, int f) {
if(u.empty()) return;
if(u.size() == 1) {
Answer(u.back(), v.back());
return;
}
int mid, last;
if(f) {
mid = u.size() - opt[u.size()];
for(int i = mid; i < v.size(); i++) {
last = Query(v[i]); cnt++;
}
} else {
mid = opt[u.size()];
for(int i = 0; i < mid; i++) {
last = Query(v[i]); cnt++;
}
}
vector<int> lu, lv(v.begin(), v.begin() + mid), ru, rv(v.begin() + mid, v.end());
for(int i = 0; i < u.size(); i++) {
if(lu.size() == lv.size()) {
ru.emplace_back(u[i]);
} else if(ru.size() == rv.size()) {
lu.emplace_back(u[i]);
} else {
int rep = Query(u[i]); cnt++;
if(rep == last) {
lu.emplace_back(u[i]);
} else {
ru.emplace_back(u[i]);
}
last = rep;
}
}
solve(lu, lv, 1);
solve(ru, rv, 0);
}
void split(vector<int> v) {
vector<int> l, r;
int last = -1;
for(int i = 0; i < v.size(); i++) {
if(r.size() == v.size() / 2) {
l.emplace_back(v[i]);
continue;
}
int rep = Query(v[i]); cnt++;
if(rep == last) {
l.emplace_back(v[i]);
} else {
r.emplace_back(v[i]);
} last = rep;
}
solve(l, r, 1);
}
void Solve(int N) {
dp[1] = 0;
for(int i = 2; i <= N; i++) {
int mn = INT_MAX, tmp, arg, cmp = (i - 1) / 2 + 1;
for(int j = 1; j < i; j++) {
tmp = dp[j] + dp[i - j] + (j < cmp ? j : i - j);
if(tmp < mn) {
mn = tmp;
arg = j;
}
}
dp[i] = mn + i;
opt[i] = arg;
}
vector<int> v(2 * N);
iota(v.begin(), v.end(), 1);
split(v);
assert(cnt <= 999975);
}
