class Solution {
public:
    int guessNumber(int n) {
        long long l=1,r=(long long)n;
        long long mid=((long long)1+n)>>1,temp;
        while (true){
            temp=guess(mid);
            if (!temp) break;
            if (temp==1)
                l=mid+(long long)1,mid=(l+r)>>1;
            else
                r=mid-(long long)1,mid=(l+r)>>1;
        }
        return mid;
    }
};