#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
// #define int long long
typedef long long ll ;
const ll ooo = 1e14 ;
const ll oo = 2e9 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7 ;
const int N = 10000010 ;
int binary(int lo , int hi , vector<int> l , vector<int> r){
if(lo > hi) return -1;
int md = (lo + hi) / 2;
vector<int> res = ask(md);
if(res[0] + res[1] == 0) return md;
int ans = -1;
int ra = rand() % 2;
if(ra){
if(res[1] > 0 && res != l) ans = binary(md+1 , hi , l , res);
if(ans == -1 && res[0] > 0 && res != r) ans = binary(lo , md - 1 , res , r);
}else {
if( res[0] > 0 && res != r) ans = binary(lo , md - 1 , res , r);
if(ans == -1 && res[1] > 0 && res != l) ans = binary(md+1 , hi , l , res);
}
return ans ;
}
int find_best(int n) {
srand (time(NULL));
vector<int> x(2 , -1);
return binary(0 , n - 1 , x , x);
}
