#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
map<int, vector<int>> mvi;
int ct = 0;
vector<int> ask2(int i) {
ct++;
if (ct == 9999) {
while (1) {
}
}
if (mvi.count(i))
return mvi[i];
return mvi[i] = ask(i);
}
int find_best(int n) {
int mk = min((int)sqrt(n) + 5, n);
int mx = -1;
int n1, n2;
int lst = -1;
int ct = 0;
for (int i = 0; i < mk; i++) {
auto vi = ask2(i);
if (vi[0] + vi[1] == 0) {
return i;
}
if (vi[0] + vi[1] >= mx) {
n1 = vi[0], n2 = vi[1];
mx = vi[0] + vi[1];
}
}
lst = mk - 1;
while (1) {
int l = lst + 1, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
auto vi = ask2(mid);
if (vi[0] + vi[1] == mx) {
if (vi[0] > n1) {
r = mid - 1;
} else {
l = mid + 1;
}
} else if (vi[0] + vi[1] == 0) {
return mid;
} else {
r = mid;
}
}
auto vi = ask2(l);
if (vi[0] + vi[1] == 0) {
return l;
}
lst = l;
while (lst < n) {
auto vi = ask2(lst);
if (vi[0] + vi[1] == mx) {
n1 = vi[0], n2 = vi[1];
break;
} else if (vi[0] + vi[1] == 0) {
return lst;
}
lst++;
}
}
}
