#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#ifdef tabr
vector<int> ask(int i);
#else
#include "prize.h"
#endif
int find_best(int n) {
if (n <= 5000) {
for (int i = 0; i < n; i++) {
auto a = ask(i);
if (a[0] + a[1] == 0) {
return i;
}
}
assert(false);
}
vector<vector<int>> res(n);
int B = (int) sqrt(n);
set<int> st;
for (int i = 0; i < n; i++) {
st.emplace(i);
}
auto Ask = [&](int i) {
if (!res[i].empty()) {
return res[i][0] + res[i][1];
}
st.erase(i);
res[i] = ask(i);
return res[i][0] + res[i][1];
};
vector<int> sz(B + 1);
for (int i = 0; i < B; i++) {
sz[i + 1] = sz[i] + (n + i) / B;
}
int mx = -1;
for (int i = 0; i < B; i++) {
mx = max(mx, Ask(sz[i]));
}
for (int i = 0; i < B; i++) {
if (Ask(sz[i]) == mx) {
continue;
}
for (int j = sz[i] + 1; j < sz[i + 1]; j++) {
if (Ask(j) == mx) {
break;
}
}
}
for (int i = 0; i < n; i++) {
if (res[i].empty() && Ask(i) == 0) {
return i;
}
}
function<void(int, int, int)> solve = [&](int low, int high, int cnt) {
if (cnt == 0) {
return;
}
assert(cnt > 0);
assert(Ask(low - 1) == mx);
int mid = (high + low) >> 1;
for (int i = mid; i < high; i++) {
if (Ask(i) == mx) {
int c = res[i][0] - res[low - 1][0] - (i - mid);
solve(low, mid, c);
solve(i + 1, high, cnt - c);
return;
}
cnt--;
}
solve(low, mid, cnt);
};
for (int k = 0; k < B; k++) {
int low = *st.lower_bound(sz[k]) - 1;
int high = *st.lower_bound(sz[k + 1]) - 1;
if (low == high) {
continue;
}
int cnt = res[high][0] - res[low][0] - (high - sz[k]);
low++;
high = sz[k + 1];
solve(low, high, cnt);
for (int i = sz[k]; i < sz[k + 1]; i++) {
if (!res[i].empty() && Ask(i) == 0) {
return i;
}
}
}
assert(false);
return -1;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}
#endif
