#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> vmid = ask(mid);
if (vmid[0] + vmid[1] == 0) {
ans = mid;
return;
}
if (vmid[0] + vmid[1] == smax) {
if (vmid[0] > lval) getans(l,mid-1,lval,vmid[1]);
if (vmid[1] > rval) getans(mid+1,r,vmid[0],rval);
return;
}
int curr = mid+1;
int curl = mid-1;
vector <int> resr,resl;
bool okl = false;
bool okr = false;
while (curr <= r) {
resr = ask(curr);
if (resr[0] + resr[1] == 0) {
ans = curr;
return;
}
if (resr[0] + resr[1] == smax) {
okr = true;
break;
}
curr++;
}
while (curl >= l) {
resl = ask(curl);
if (resl[0] + resl[1] == 0) {
ans = curl;
return;
}
if (resl[0] + resl[1] == smax) {
okl = true;
break;
}
curl--;
}
if (okr) {
if (resr[1] > rval) getans(curr+1, r, resr[0], rval);
}
if (okl) {
if (resl[0] > lval) getans(l, curl-1, lval, resl[1]);
}
}
int find_best(int n) {
vector <int> res;
for(int i = 0; i < min(n,475); i++) {
res = ask(i);
smax = max(smax,res[0] + res[1]);
}
getans(0,n-1,0,0);
return ans;
}
