#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
int find_best(int n){
int ct=50,V=n;
while(ct--){
int x=rng()%n;
vector<int>tmp=ask(x);
if(n-(tmp[0]+tmp[1])<V) V=n-(tmp[0]+tmp[1]);
}
int res=-1;
set<int>st;
st.insert(-1),st.insert(n);
auto it=st.begin();
while(it!=st.end()){
auto it2=it;
int i=*it;
if(res!=-1 && res==i) break;
it++;
if(it==st.end()) break;
int j=*it;
int l=i+1,r=j-1;
//printf("%i %i\n",i,j);
while(l<=r){
int mid=(l+r)/2;
vector<int>tmp=ask(mid);
if(n-tmp[0]-tmp[1]!=V){
if(tmp[0]==0 && tmp[1]==0) res=mid;
st.insert(mid);
r=mid-1;
continue;
}
if(tmp[0]>=1) r=mid-1;
else l=mid+1;
}
it=it2;
it++;
}
/*for(int i = 0; i < n; i++) {
std::vector<int> res = ask(i);
if(res[0] + res[1] == 0)
return i;
}*/
return res;
}
