#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int smax = 0;
int ans = -1;
void getans(int l, int r, int cnt, int lval, int rval) {
if (!cnt) return;
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) {
int vl = vmid[0]-lval;
int vr = vmid[1]-rval;
if (vmid[0] > lval) getans(l,mid-1, vl, lval,vmid[1]);
if (vmid[1] > rval) getans(mid+1,r, vr,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--;
}
int vl = -1;
int vr = -1;
if (okl) {
vl = resl[0]-lval;
}
if (okr) {
vr = resr[0]-rval;
}
if (okl) {
if (resl[0] > lval) getans(l, curl-1, vl,lval, resl[1]);
}
if (okr) {
if (resr[1] > rval) getans(curr+1, r,vr,resr[0], rval);
}
}
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,smax,0,0);
return ans;
}
