#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int find_best(int n) {
if (n == 1) {
return 0;
}
int S = sqrt(n);
if (S * S < n) {
S++;
}
int pos = 0;
int big = 0;
for (int i = 0; i <= S * 2; i++) {
vector <int> res = ask(i);
if (res[0] == 0 && res[1] == 0) {
return i;
}
big = max(big, res[0] + res[1]);
}
pos = S + 1;
while(1) {
vector <int> pres = ask(pos);
if (pres[0] == 0 && pres[1] == 0) {
return pos;
}
if (pres[0] + pres[1] == big) {
int l = pos, r = n;
while(r - l > 1) {
int mid = (l + r) >> 1;
vector <int> mres = ask(mid);
if (pres[0] == mres[0] && pres[1] == mres[1]) {
l = mid;
} else {
r = mid;
}
}
pos = l + 1;
} else {
pos++;
}
}
}
