#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int HOTTER = 1, COLDER = -1, SAME = 0;
template <class Func>
int FIND_SMALLEST(int l, int r, Func f) {
int res = r + 1;
while (l <= r) {
int m = (l + r) >> 1;
if (f(m)) res = m, r = m - 1;
else l = m + 1;
}
return res;
}
template <class Func>
int FIND_LARGEST(int l, int r, Func f) {
int res = l - 1;
while (l <= r) {
int m = (l + r) >> 1;
if (f(m)) res = m, l = m + 1;
else r = m - 1;
}
return res;
}
int findLeft(int N) {
auto f = [&](int len) {
Guess(1);
return Guess(1 + 2 * len);
};
int l = 0, r = N / 2;
while (l <= r) {
int m = (l + r) >> 1;
int val = f(m);
if (val == SAME)
return 1 + m;
if (val == HOTTER)
l = m + 1;
else
r = m - 1;
}
return -1;
}
int findRight(int N) {
auto f = [&](int len) {
Guess(N);
return Guess(N - 2 * len);
};
int l = 0, r = N / 2;
while (l <= r) {
int m = (l + r) >> 1;
int val = f(m);
if (val == SAME)
return N - m;
if (val == HOTTER)
l = m + 1;
else
r = m - 1;
}
return -1;
}
int HC(int N) {
Guess(1);
int id = Guess(N);
if (id == SAME)
return (N + 1) / 2;
if (id == HOTTER)
return findRight(N);
return findLeft(N);
}
