#include <bits/stdc++.h>
#include "prize.h"
#define ff first
#define ss second
using namespace std;
const int maxn = 2e5+5;
int l,r,md,ans,x;
int vis[maxn],mn;
int rand(int a, int b) {
if(a > b) exit(0);
return a + rand() % (b - a + 1);
}
int find_best(int n) {
srand(time(0));
l = 0,r = n-1;
while(l <= r){
md=(l+r)/2;
vector<int> jog = ask(md);
if(jog[0] == 0 and jog[1] == 0) return md;
vis[md]=1;
if(jog[0] < jog[1]) l = md+1;
else r = md-1;
}
l = 0,r = n-1;
while(1){
x = rand(l,r);
if(vis[x]) continue;
vector<int> jog = ask(x);
if(jog[0]+jog[1]==0) return x;
vis[x]=1;
if(jog[0] + jog[1] >= mn) continue;
mn=jog[0] + jog[1];
if(jog[0] > jog[1]) l=0,r=x-1;
else l=x+1,r=n-1;
}
}
