#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
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;
if(trial[0] > 0) ans = max(ans, binarySearch(left, mid));
if(trial[1] > 0) ans = max(ans, binarySearch(mid, right));
return ans;
}
int find_best(int n) {
LeftVal = vector<int>(n, -1);
RightVal = vector<int>(n, -1);
vector<int> trial = ask(0);
LeftVal[0] = trial[0];
RightVal[0] = trial[1];
if (LeftVal[0] + RightVal[0] == 0) return 0;
trial = ask(n-1);
LeftVal[n-1] = trial[0];
RightVal[n-1] = trial[1];
if (LeftVal[n-1] + RightVal[n-1] == 0) return n-1;
return binarySearch(0, n-1);
}
