#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int LIM = 43e3;
int A[LIM], L, R = -1, last;
#define ask(Z) (last = Query(Z))
void dfs(int l, int r, vector<int> b, bool on) {
if(r - l < 1) return;
if(r - l < 2) return Answer(A[l], b[0]);
int m = (l + r) / 2;
if(l < m-1 && m - l == r - m) --m;
if(l < m-1 && m - l + 1 == r - m) --m;
if(l < m-1 && m - l + 2 == r - m) --m;
for(int i = l; i < m; ++i)
ask(A[i]);
vector<int> bL, bR;
for(int &i : b) {
if((int)size(bL) == m - l) {
bR.push_back(i);
continue;
}
if((int)size(bR) == r - m) {
bL.push_back(i);
continue;
}
int prev = last;
((prev == ask(i)) ^ on ? bL : bR).push_back(i);
}
dfs(l, m, bL, on ^ 1);
dfs(m, r, bR, on);
}
void Solve(int N) {
array<int, 2> s[N+N];
for(unsigned int i = 0, j = 12345; int(i) < N + N; ++i)
s[i] = {int((j *= 3) >> 1), int(i)+1};
sort(s, s+N+N);
vector<int> b;
for(auto &[_, i] : s) {
if(R == N - 1 || ask(i) < R + 2) {
b.push_back(i);
} else A[++R] = i;
}
dfs(0, N, b, 1);
}
