//#pragma once
//#include "grader.cpp"
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 mt(552);
int sum,lamp,nn,num=10,lf,rf,rr,used[200005];
void prec()
{
vector<int>a;
int h;
for(int i=1; i<=200; i++)
{
//h=((i*199942+7424)/3)%nn;
h=mt()%nn;
a=ask(h);
sum=max(sum,a[0]+a[1]);
a.clear();
}
/*if(nn>=105689)
{
h=105687;
a=ask(h);
sum=max(sum,a[0]+a[1]);
h--;
a=ask(h);
sum=max(sum,a[0]+a[1]);
h+=2;
a=ask(h);
sum=max(sum,a[0]+a[1]);
}*/
}
void rec(int l,int r,int br,int exl,int exr,int dul)
{
if(lamp)return;
int mid=(l+r)/2,ad=1;
vector<int>a;
while(true)
{
if(num>=9998)
{
lamp=sum+20000000;
return;
}
used[mid-1]=1;
a.clear();
a=ask(mid-1);
num++;
if(a[0]+a[1]==0)
{
lamp=mid;
return;
}
if(a[0]==0)lf=mid+1;
if(a[1]==0)rf=mid-1;
if(a[0]+a[1]==sum)
{
break;
}
else rr=mid-1;
mid+=ad;
if(mid>r)
{
mid=(l+r)/2-1;
ad=-1;
}
if(mid<l)return;
}
int dist=abs(mid-(l+r)/2);
if(mid>=(l+r)/2)
{
//if(a[1]-exr>0&&a[0]-exl-dist>0)rr++;
if(a[1]-exr>0)rec(mid+1,r,a[1]-exr,a[0],exr,dul+1);
if(a[0]-exl-dist>0)rec(l,(l+r)/2-1,a[0]-exl-dist,exl,a[1]+dist,dul+1);
}
else
{
if(a[0]-exl>0)rec(l,mid-1,a[0]-exl,exl,a[1],dul+1);
}
}
int find_best(int N)
{
nn=N;
rf=N;
prec();
rec(1,nn,sum,0,0,1);
return lamp-1;
}
