#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
map<int,vector<int>> mp;
vector<int> q(int idx) {
if (mp.find(idx) != mp.end()) return mp[idx];
vector<int> res = ask(idx);
mp[idx] = res;
return res;
}
int find_best(int n) {
mp.clear();
int l = 0, r = n-1;
while (l <= r) {
int m = l+(r-l)/2;
vector<int> res = q(m);
int ll = res[0], rr = res[1];
if (ll+rr == n-1) return m;
if (ll>rr) r = m-1;
else l = m+1;
}
for (int i = 0; i < n; i++) {
vector<int> res = q(i);
if (res[0]+res[1] == n-1) return i;
}
return 0;
}
