#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int random(int l, int r) {
return uniform_int_distribution <int> (l, r)(rng);
}
#define pii pair <int, int>
#define fi first
#define se second
const int MAXN = 50000;
vector <int> events[MAXN];
void Solve(int N) {
vector <int> L, R;
for (int i = 1; i <= 2 * N; i++) {
if (Query(i) == L.size() + 1) L.emplace_back(i);
else {
Query(i);
R.emplace_back(i);
}
}
for (int &x: L) Query(x);
vector <pii> range(N, make_pair(0, N - 1));
vector <bool> remove(N);
while (true) {
for (int i = 0; i < N; i++) {
if (range[i].fi == range[i].se) {
remove[range[i].fi] = true;
}
}
vector <int> remain;
for (int i = 0; i < N; i++)
if (!remove[i]) remain.emplace_back(i);
if (remain.empty()) break;
// cerr << remain.size() << endl;
for (int i = 0; i < remain.size(); i++)
events[i].clear();
int maId = -1;
for (int i = 0; i < N; i++) if (range[i].fi != range[i].se) {
int l = lower_bound(remain.begin(), remain.end(), range[i].fi) - remain.begin();
int r = upper_bound(remain.begin(), remain.end(), range[i].se) - remain.begin() - 1;
if (range[i].fi == range[i].se) range[i].fi = range[i].se = remain[l];
else {
range[i] = make_pair(remain[l], remain[r]);
int mid = (l + r) >> 1;
events[mid].emplace_back(i);
maId = max(maId, mid);
}
}
if (maId == -1) break;
for (int i = 0; i <= maId; i++) {
Query(R[remain[i]]);
for (int &l: events[i]) {
int tmp = Query(L[l]); Query(L[l]);
if (tmp == i + 1) range[l].se = remain[i];
else range[l].fi = remain[i + 1];
}
}
for (int i = 0; i <= maId; i++) Query(R[remain[i]]);
}
for (int i = 0; i < N; i++)
Answer(L[i], R[range[i].fi]);
}
