#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int smax = 0;
int ans = -1;
void getans(int l, int r, int lval, int rval) {
if (ans != -1) return;
if (l > r) return;
int mid = (l+r)/2;
vector <int> res = ask(mid);
int sum = res[0] + res[1];
if (sum == 0) {
ans = mid;
return;
}
if (sum < smax) {
int lmid = mid-1;
res = ask(lmid);
while (lmid >= l) {
if (res[0] + res[1] == 0) {
ans = lmid;
return;
}
if (res[0] + res[1] == smax) break;
lmid--;
res = ask(lmid);
}
getans(l,lmid,lval,res[1]);
int rmid = mid+1;
res = ask(rmid);
while (rmid <= r) {
if (res[0] + res[1] == 0) {
ans = rmid;
return;
}
if (res[0] + res[1] == smax) break;
rmid++;
res = ask(rmid);
}
getans(rmid,r,res[0],rval);
} else {
if (res[0] > lval) {
getans(l,mid-1,lval,res[1]);
}
if (res[1] > rval) {
getans(mid+1,r,res[0],rval);
}
}
}
int find_best(int n) {
vector <int> res;
for(int i = 0; i < min(n,500); i++) {
res = ask(i);
smax = max(smax,res[0] + res[1]);
}
getans(0,n-1,0,0);
return ans;
}
