#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
vector<int> isi[maxn+2];
vector<int>query(int idx){
if(isi[idx][0]!=-1)return isi[idx];
isi[idx]=ask(idx);
return isi[idx];
}
int sum(int idx){
if(isi[idx][0]==-1)isi[idx]=ask(idx);
return isi[idx][0]+isi[idx][1];
}
int find_best(int n) {
for(int q=0;q<n;q++)isi[q]={-1,-1};
isi[0]=query(0);
if(sum(0)==0)return 0;
int cur=0;
while(cur<n){
query(cur);
if(sum(cur)==0)return cur;
if(sum(cur)<sum(0)){
cur++; continue;
}
int l=cur+1,r=n-1,nxt=n;
while(l<=r){
int mid=(l+r)/2;
query(mid);
if(sum(mid)==0)return mid;
if(isi[mid][1]==isi[cur][1]){
l=mid+1;
}
else{
nxt=mid; r=mid-1;
}
}
cur=nxt;
}
return cur;
}
