#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> LeftVal, RightVal;
int binarySearch(int left, int right){
int ans = -1;
if(left+1 >= right) return -1;
int mid = left + (right - left)/2;
vector<int> trial = ask(mid);
LeftVal[mid] = trial[0];
RightVal[mid] = trial[1];
if((trial[0] +trial[1]) == 0) return mid;
int myRight = mid;
int myLeft = mid;
while((LeftVal[myLeft] + RightVal[myLeft]) < (LeftVal[left] + RightVal[left])){
myLeft--;
trial = ask(myLeft);
LeftVal[myLeft] = trial[0];
RightVal[myLeft] = trial[1];
if((trial[0]+trial[1]) == 0) return myLeft;
}
while(((LeftVal[myRight] + RightVal[myRight]) < (LeftVal[left] + RightVal[left])) and (myRight < right)){
myRight++;
trial = ask(myRight);
LeftVal[myRight] = trial[0];
RightVal[myRight] = trial[1];
if((trial[0]+trial[1]) == 0) return myRight;
}
if((LeftVal[myLeft] - LeftVal[left]) > 0) ans = max(ans, binarySearch(left, myLeft));
if(myRight < right){
if(right == N){
if(RightVal[myRight] > 0) ans = max(ans, binarySearch(myRight, right));
}
else{
if((RightVal[myRight] - RightVal[right])> 0) ans = max(ans, binarySearch(myRight, right));
}
}
return ans;
}
int find_best(int n) {
N = n;
LeftVal = vector<int>(n, -1);
RightVal = vector<int>(n, -1);
vector<int> trial = ask(0);
int lollipop = 0;
LeftVal[0] = trial[0];
RightVal[0] = trial[1];
if((LeftVal[0] + RightVal[0]) == 0) return 0;
for(int i = 1; i < min(n, 500); ++i){
trial = ask(i);
LeftVal[i] = trial[0];
RightVal[i] = trial[1];
if((LeftVal[i]+RightVal[i]) >= (LeftVal[lollipop] + RightVal[lollipop])) lollipop = i;
if((LeftVal[i] + RightVal[i]) == 0) return i;
}
return binarySearch(lollipop, n-1);
}
