#include "minerals.h"
#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>
void Solve(int n) {
int old = Query(1);
std::vector<int> distinct = {1}, repeated;
for (int i = 2; i <= 2 * n; ++i) {
int nval = Query(i);
if (old != nval) {
distinct.push_back(i);
} else {
repeated.push_back(i);
}
old = nval;
}
std::vector<int> p(2 * n + 1);
for (int i = 1; i <= n; ++i) {
p[i] = distinct[i - 1];
}
for (int i = n + 1; i <= 2 * n; ++i) {
p[i] = repeated[i - n - 1];
}
for (int i = 1; i <= 2 * n; ++i) {
Query(i);
}
auto query = [&](int i) {
return Query(p[i]);
};
auto answer = [&](int a, int b) {
Answer(p[a], p[b]);
};
std::vector<int> set1(n), set2(n);
std::iota(set1.begin(), set1.end(), 1);
std::iota(set2.begin(), set2.end(), n + 1);
// before dnc: set1 == set2
// make dnc step make it so
// set1 left half == set2 left half (then set1 right half is automatically == set2 right half)
auto solve = [&](auto &&self, int l, int r, bool added) {
if (l == r) {
answer(set1[l], set2[l]);
return;
}
int m = (l + r) / 2;
// add to machine
int p = -1;
for (int i = l; i <= m and !added; ++i) {
p = query(set1[i]);
}
// now both parts are good
std::partition(set2.begin() + l, set2.begin() + r + 1, [&](int x) {
int n = query(x);
bool unchanged = p == n;
p = n;
return unchanged;
});
// do dnc
self(self, l, m, true);
self(self, m + 1, r, false);
};
solve(solve, 0, n - 1, false);
}
