#include "prize.h"
using namespace std;
#include <bits/stdc++.h>
map<int, vector<int>> rem;
vector<int> myAsk(int pos) {
if (rem.count(pos)) return rem[pos];
return rem[pos] = ask(pos);
}
int getNumBetter(vector<int> x) {
return x[0]+x[1];
}
int find_best(int n) {
rem.clear();
int numBetter = 0;
int ind = 0;
for (int i = 0; i<min(n, 1000); i++) {
int hereBetter = getNumBetter(myAsk(i));
if (hereBetter > numBetter) {
numBetter = hereBetter;
ind = i;
}
}
set<int> candidates;
for (int i=0; i<ind; i++) candidates.insert(i);
int pos = ind;
while (true) {
int l = pos+1, r = n-1;
while (l<r) {
int m = (l+r)/2;
vector<int> ans = myAsk(m);
if (getNumBetter(ans) < numBetter) {
r = m;
continue;
}
if (ans[1] < numBetter-(int)candidates.size()) {
r = m;
}
else l = m+1;
}
pos = l;
while (pos < n && getNumBetter(myAsk(pos)) < numBetter) {
candidates.insert(pos);
pos++;
}
if ((int)candidates.size() == numBetter) break;
}
for (int i: candidates) {
if (getNumBetter(myAsk(i)) == 0) return i;
}
assert(0);
}
