#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int smax = 0;
int ans = -1;
int n;
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);
int curr = mid+1;
int curl = mid-1;
vector <int> resr,resl;
while (curr <= r) {
resr = ask(curr);
if (resr[0] + resr[1] == 0) {
ans = curr;
return;
}
if (resr[0] + resr[1] == smax) break;
curr++;
}
while (curl >= l) {
resl = ask(curl);
if (resl[0] + resl[1] == 0) {
ans = curl;
return;
}
if (resl[0] + resl[1] == smax) break;
curl--;
}
if (curr <= r) {
getans(curr, r, resr[0], rval);
}
if (curl >= l) {
getans(l, curl, lval, resl[1]);
}
}
int find_best(int N) {
int n = 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;
}
