#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
vector<vector<int>> cache(n, vector<int>(2, -1));
int queries = 0;
auto uwu = [&](int i) {
if (cache[i] != vector<int>(2, -1)) {
return cache[i];
}
queries++;
assert(queries < 10000);
return cache[i] = ask(i);
};
int mx = 0, ptr = 0;
for (int i = 0; i < min(450, n); i++) {
vector<int> v = uwu(i);
if (v[0] + v[1] > mx) {
mx = v[0] + v[1];
ptr = i;
}
}
while (ptr < n) {
vector<int> v1 = uwu(ptr);
if (v1[0] + v1[1] == mx) {
int low = ptr, high = n - 1, idx = -1;
while (low <= high) {
int mid = (low + high) >> 1;
vector<int> v2 = uwu(mid);
if (v2[1] == v1[1]) {
idx = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
ptr = idx + 1;
} else {
if (v1[0] + v1[1] == 0) {
return ptr;
}
ptr += 1;
}
}
return -1;
}
