#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int res=-1;
bool check=false;
vector<vector<int>>v;
void dvq(int l,int r)
{
if(check)return;
if(r-l<2)return;
int m=(l+r)/2;
auto temp=ask(m);
v[m][0]=temp[0];
v[m][1]=temp[1];
if(v[m][0]+v[m][1]==0)
{
res=m;
check=true;
return;
}
if(v[m][0]+v[m][1]==v[l][1]+v[l][0])
{
if(v[m][0]-v[l][0]!=0)dvq(l,m);
}
else if(v[m][0]!=0)dvq(l,m);
if(v[m][0]+v[m][1]==v[r][1]+v[r][0])
{
if(v[m][1]-v[r][1]!=0)dvq(m,r);
}
else if(v[m][1]!=0)dvq(m,r);
}
int find_best(int n)
{
v.resize(n);
for(int i=0;i<n;i++)
{
v[i].resize(2);
}
auto temp=ask(0);
v[0][0]=temp[0];
v[0][1]=temp[1];
if(v[0][0]+v[0][1]==0)return 0;
temp=ask(n-1);
v[n-1][0]=temp[0];
v[n-1][1]=temp[1];
if(v[n-1][0]+v[n-1][1]==0)return n-1;
dvq(0,n-1);
return res;
}
