#include<bits/stdc++.h>
using namespace std;
int Guess(int n);
// int lastG = -1, X;
// int cnt = 0;
// int Guess(int n){
// cnt++;
// // cout << "GUESS: " << lastG << ", " << n << '\n';
// if(lastG == -1 || abs(X - lastG) == abs(X - n)){
// lastG = n;
// return 0;
// }
// if(abs(X - lastG) > abs(X - n)){
// lastG = n;
// return 1;
// }
// lastG = n;
// return -1;
// }
int HC(int n){
int l = 1, r = n;
int last = 1;
Guess(1);
while(l < r){
int mid = (l + r) / 2;
// cout << "[" << l << ", " << r << "]\n";
if(mid == last)mid++;
int num = Guess(mid);
if(num == 1){
if(last < mid){
l = (last + mid) / 2 + 1;
}
else{
r = (last + mid) / 2;
}
}
else if(num == -1){
if(last < mid){
r = (last + mid) / 2;
}
else{
l = (last + mid) / 2 + 1;
}
}
else{
return (last + mid) / 2;
}
last = mid;
}
return l;
}
// int main(){
// int COUNTER = 0;
// for(int i = 1;i <= 500;++i){
// for(int j = 1;j <= i;++j){
// X = j;
// cnt = 0;
// lastG = -1;
// int found_num = HC(i);
// if(found_num != j){
// cout << "Wrong Answer: " << i << ", " << j << '\n';
// cout << "FOUND: " << found_num << '\n';
// break;
// }
// else if(cnt > 15){
// COUNTER++;
// cout << i << ", " << j << ": " << cnt << '\n';
// }
// }
// }
// cout << COUNTER;
// // X = 2;
// // cout << HC(2) << '\n';
// // cout << cnt;
// }
