#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
bool go_lg(int &bg,int &en,int &tmp)
{
if(tmp==0)
return true;
else if(tmp==-1)
en=(bg+en-1)/2;
else
bg=(bg+en+2)/2;
return false;
}
bool go_gl(int &bg,int &en,int &tmp)
{
if(tmp==0)
return true;
else if(tmp==1)
en=(bg+en-1)/2;
else
bg=(bg+en+2)/2;
return false;
}
int HC(int N)
{
if(N==1)
return 1;
if(N==2)
{
Guess(1);
int tmp=Guess(2);
if(tmp==1)
return 2;
return 1;
}
mt19937 gen(2913319);
int bg=1,en=N;
int l=-1;
while(bg<en)
{
//cerr<<bg<<" "<<en<<" "<<l<<"\n";
if(l==bg)
{
int nl=en;
int tmp=Guess(nl);
if(go_lg(bg,en,tmp))
return (bg+en)/2;
l=nl;
}
else if(l==en)
{
int nl=bg;
int tmp=Guess(nl);
if(go_gl(bg,en,tmp))
return (bg+en)/2;
l=nl;
}
else
{
l=(bg+en-1)/2;
int nl=(bg+en+2)/2;
if(uniform_int_distribution<int>{0,1}(gen))
{
Guess(nl);
int tmp=Guess(l);
if(tmp==0)
return (bg+en)/2;
else if(tmp==1)
en=l;
else if((en-bg+1)<4)
bg=nl;
else
bg=l;
}
else
{
Guess(l);
int tmp=Guess(nl);
if(tmp==0)
return (bg+en)/2;
else if(tmp==1)
bg=nl;
else if((en-bg+1)<4)
en=l;
else
en=nl;
l=nl;
}
}
}
return bg;
}
