#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int HC(int n)
{
if (n == 1) return 1;
int ini = 1, fim = n;
while (ini < fim)
{
if (fim-ini == 1)
{
Guess(ini);
int g = Guess(fim);
return (g == -1 ? ini : fim);
}
int delta = (fim-ini+1)/3;
int mid1 = ini + delta - 1;
int mid2 = fim - delta + 1;
Guess(mid1);
int g = Guess(mid2);
if (g == 0) return (mid1+mid2)/2;
else if (g == 1)
{
if (fim-ini == 2) return fim;
ini = (mid1+mid2)/2 + 1;
}
else
{
if (fim-ini == 2) return ini;
fim = (mid1+mid2)/2;
if ((mid1+mid2)%2 == 0) fim--;
}
}
return ini;
}
