#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int HC(int N){
int l=1,r=N;
int a;
int prevv = -1;
a = Guess(1);
bool left = true;
while(l<r){
//std::cout << l << "\t" << r << '\n';
int mid = (l+r)/2;
if(mid==prevv)mid++;
prevv = mid;
if(left){
a = Guess(r);
//std::cout << l << "\t" << r << '\t' << mid <<'\n';
if(a==1)//close to r
l = mid;
else{//close to l
r= mid;
Guess(r);
}
}else{
a = Guess(l);
//std::cout << l << "\t" << r << '\t' << mid <<'\n';
if(a==1)//close to l
r = mid;
else{//close to r
l= mid;
Guess(l);
}
}
left^=1;
}
return l;
}
