#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 gen(64920);
uniform_int_distribution<int> dist(0, 1);
int HC(int N){
int lt = 1;
int rt = N;
int prv = -1;
while (lt < rt) {
int res = -2;
if (prv == lt) {
res = Guess(rt);
prv = rt;
}
else if (prv == rt) {
res = -Guess(lt);
prv = lt;
}
else if (dist(gen) == 0) {
Guess(lt);
res = Guess(rt);
prv = rt;
}
else {
Guess(rt);
res = -Guess(lt);
prv = lt;
}
if (res == 0) {
return (lt + rt) / 2;
}
if (res == 1) {
lt = (lt + rt) / 2 + 1;
}
else {
rt = (lt + rt - 1) / 2;
}
}
return lt;
}
