#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
if (n <= 10000) {
for (int i = 0; i < n; i++) {
vector<int> ret = ask(i);
if (ret[0] + ret[1] == 0) return i;
}
assert(false);
return -1;
}
int ll = 0, rr = n-1;
int need = 0;
vector<int> lastTot;
for (int i = 0; i < 500; i++) {
vector<int> curr = ask(i);
need = max(need, curr[0] + curr[1]);
if (curr[0] + curr[1] == 0) return i;
if (curr[0] + curr[1] == need) {
ll = i;
lastTot = curr;
}
}
while (true) {
int lo = ll+1, hi = rr;
int idx = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
vector<int> tot = ask(mid);
if (tot[0] + tot[1] == 0) return mid;
if (tot[0] + tot[1] < need) {
idx = mid;
hi = mid-1;
continue;
}
int toL = tot[0] - lastTot[0];
if (toL) {
hi = mid-1;
}
else lo = mid+1;
}
assert(idx != -1);
ll = idx+1;
lastTot = ask(ll);
while (lastTot[0] + lastTot[1] != need) {
if (lastTot[0] + lastTot[1] == 0) return ll;
ll++;
lastTot = ask(ll);
}
}
}
