#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int mxsum = 0;
bool ismx(vector<int> ans){
int s = ans[0] + ans[1];
return s == mxsum;
}
int find_best(int N) {
for(int i = 0; i < min(N, 711); i++){
vector<int> ans = ask(i);
int s = ans[0] + ans[1];
if(ans[0] + ans[1] == 0){
return i;
}
if(s > mxsum) mxsum = s;
}
int idx = 0;
while(1){
vector<int> ori;
while(1){
vector<int> ans = ask(idx);
if(ismx(ans)) {
ori = ans;
break;
}
if(ans[0] + ans[1] == 0){
return idx;
}
idx++;
}
// ori should always have length here
// there should always be positive amount lower here
int l = idx, r = N - 1;
while(l < r){
int m = (l + r) / 2;
auto ans = ask(m);
if(ans[0] + ans[1] == 0){
return m;
}
if(ans[1] == ori[1]){
l = m + 1;
}else if(ans[1] < ori[1]){
r = m - 1;
}
}
if(ask(l)[1] == ori[1]){
idx = l + 1;
}else{
idx = l;
}
}
return -1;
}
