#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> dp[200002];
bool done[200002][2];
int find_best(int n) {
//memset(dp,-1,sizeof dp);
int idx=(n-1)/2;
for (int q = 50; q >=0 ; q--)
{
int l,r;
vector<int> res;
//if(!dp[idx].empty())res=dp[idx];
res=ask(idx);
//cerr<<q<<"\n";
if(res[0]+res[1]==0)return idx;
if(res[1]>=res[0])l=idx+1,r=n-1;
else r=idx-1,l=0;
idx=(l+r)/2;
while(l<r){
//cerr<<l<<" "<<r<<"\n";
int med=(l+r)/2;
res=ask(med);
if(res[0]+res[1]==0)return med;
//cerr<<med<<"\n";
if(res[1]>=res[0]&&!done[med][1])done[med][1]=1,l=med+1,idx=l;
else if(!done[med][0])done[med][0]=1,r=med-1,idx=r;
else break;
}
}
return 0;
}
