#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int mx=0;
int HC(int N){
int l=1,r=N,m,p,cnt=1,tmp;
int s=0;
Guess(l);
tmp=Guess(r);s+=2;
for(;;){
// printf("l=%d r=%d\n",l,r);
m=(l+r)/2;p=(l+r)%2;
if (tmp==0){
// printf("ans=%d\nQuery=%d\n",m,s);
return m;
}
else if (tmp==1){
if (cnt==1){
l=m+1,cnt=0;
if (l==r){
// printf("ans=%d\nQuery=%d\n",l,s);
return l;
}
tmp=Guess(l);s+=1;
if (l+1==r){
// printf("ans=%dor%d\nQuery=%d\n",l,r,s);
if (tmp==1)return l;
else return r;
}
}
else{
r=m,cnt=1;
if(p==0)r--;
if (l==r){
// printf("ans=%d\nQuery=%d\n",l,s);
return l;
}
tmp=Guess(r);s+=1;
if (l+1==r){
// printf("ans=%dor%d\nQuery=%d\n",l,r,s);
if (tmp==1)return r;
else return l;
}
}
}else{//tmp==-1
if (cnt==1){
r=m,cnt=1;
if(p==0)r--;
if (l==r){
// printf("ans=%d\nQuery=%d\n",l,s);
return l;
}
Guess(l);
tmp=Guess(r);s+=2;
if (l+1==r){
// printf("ans=%dor%d\nQuery=%d\n",l,r,s);
if (tmp==1)return r;
else return l;
}
}else{
l=m+1,cnt=0;
if (l==r){
// printf("ans=%d\nQuery=%d\n",l,s);
return l;
}
Guess(r);
tmp=Guess(l);s+=2;
if (l+1==r){
// printf("ans=%dor%d\nQuery=%d\n",l,r,s);
if (tmp==1)return l;
else return r;
}
}
}
}
}
