//#include "grader.cpp"
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 mt(time(nullptr));
int sum,lamp,n;
vector<int>a;
void prec()
{
for(int i=1;i<=5;i++)
{
a=(ask(mt()%n));
sum=max(sum,a[0]+a[1]);
}
}
void rec(int l,int r,int br,int exl,int exr)
{
if(lamp||!br)return;
int mid=(l+r)/2;
a=ask(mid);
if(a[0]+a[1]==0)
{
lamp=mid+1;
return;
}
rec(l,mid-1,a[0]-exl,exl,a[1]);
rec(mid+1,r,a[1]-exr,a[0],exr);
}
int find_best(int N)
{
n=N;
prec();
rec(1,n,sum,0,0);
return lamp-1;
}
