#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
int test(vector<int> q)
{
if(q[0]==0&&q[1]==0)return 1;
return 0;
}
vector<int> arr;
int ans;
void solve(int l,vector<int> arr_l,int r,vector<int> arr_r)
{
if(r-l<=1)return;
if(arr_l==arr_r)return;
if(ans!=-1)return;
int av=(l+r)/2;
vector<int> arr_av=ask(av);
if(test(arr_av))
{
ans=av;
return;
}
if(arr_l[0]+arr_l[1]==arr_r[0]+arr_r[1])
{
if(arr_av[0]+arr_av[1]<arr_l[0]+arr_l[1]&&arr_l[0]==arr_r[0]-1)return;
}
if(rand()%2)
{
solve(l,arr_l,av,arr_av);
solve(av,arr_av,r,arr_r);
}
else
{
solve(av,arr_av,r,arr_r);
solve(l,arr_l,av,arr_av);
}
}
int find_best(int n)
{
srand(time(0));
vector<int> l=ask(0);
if(test(l))return 0;
vector<int> r=ask(n-1);
if(test(r))return n-1;
ans=-1;
solve(0,l,n-1,r);
return ans;
}
