#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;
}
mt19937 rnd(time(NULL));
int solve(int l, int r, int old = 0) {
if (l == r)
return r;
/*
if (old != 0)
cout << "solve " << l << " " << r << ", old = " << old << endl;
*/
if (old == l) {
int id = Guess(r);
int m = (l + r) >> 1;
if (id == SAME)
return m;
if (id == HOTTER)
return solve(m + 1, r, r);
return solve(l, m, 0);
}
if (old == r) {
int id = Guess(l);
int m = (l + r + 1) >> 1;
if (id == SAME)
return m;
if (id == HOTTER)
return solve(l, m - 1, l);
return solve(m, r, 0);
}
int x = (rnd() & 1) ? l : r;
Guess(x);
return solve(l, r, x);
}
int HC(int N) {
return solve(1, N);
}
