#include "guess.h" 
#include <random>
#include <ctime>

int solve(int n) { 
    srand(time(0));
    int l = 1, r = n, mid, ans;
    while(l<=r) {
        mid=l; if(l!=r) mid = l+rand()%(r-l+1);
        if(query(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    return ans;
}