#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rng(1557);
int HC(int N){
int l = 1, r = N, p = -1;
while(l<r){
bool flagL = (p<=l && r+l-p<=N);
bool flagR = (p>=r && r+l-p>=1);
if (!flagL && !flagR){
if (rng()&1) p = max((l*2+r)/3-1, l), Guess(p), flagL = true;
else p = min((l+r*2)/3+1, r), Guess(p), flagR = true;
}
int ret;
if (flagL){
p = r+l-p, ret = Guess(p);
if (ret==0) return (l+r) / 2;
else if (ret==1) l = (l+r) / 2 + 1;
else r = (l+r-1) / 2;
}
else{
p = r+l-p, ret = Guess(p);
if (ret==0) return (l+r) / 2;
else if (ret==-1) l = (l+r) / 2 + 1;
else r = (l+r-1) / 2;
}
}
return l;
}
