#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<int, int>;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int((x).size()))
#define pb push_back
#define f first
#define s second
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rev(i, a, b) for (int i = (a); i >= (b); i--)
template<class T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<class T> bool chmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}
const int INF = 1e9 + 5;
const ll LINF = 4e18;
#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << (x) << endl;
#else
#define dbg(x)
#endif
int T = 0, Q = 0;
map<int, pi> cache;
pi query(int i) {
T++;
if (cache.count(i)) return cache[i];
Q++;
vi res = ask(i);
return cache[i] = {res[0], res[1]};
}
bool is_diamond(pi x) {
return x.f == x.s && x.s == 0;
}
int find_best(int n) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi-lo)/2;
auto r = query(mid);
if (is_diamond(r)) return mid;
if (r.f == 1) hi = mid;
else lo = mid + 1;
}
return lo-1;
}
