#include "prize.h"
using namespace std;
#include <bits/stdc++.h>
int numBetter = 0;
map<int, vector<int>> rem;
set<pair<int, int>> BSstuff;
int getNumBetter(vector<int> x) {
return x[0]+x[1];
}
vector<int> myAsk(int pos) {
if (rem.count(pos)) return rem[pos];
rem[pos] = ask(pos);
if (getNumBetter(rem[pos]) == numBetter) {
BSstuff.insert({-rem[pos][1], pos});
}
return rem[pos];
}
int find_best(int n) {
// srand(n+654);
// int randNumBetter = 0;
// for (int i = 0; i<5; i++) {
// int hereBetter = getNumBetter(myAsk(rand()%n));
// if (hereBetter > numBetter) {
// randNumBetter = hereBetter;
// }
// }
numBetter=0;
rem.clear();
BSstuff.clear();
BSstuff.insert({-1e9, 0});
BSstuff.insert({1e9, n-1});
int ind = 0;
for (int i = 0; i<min(n, 1000); i++) {
int hereBetter = getNumBetter(myAsk(i));
if (hereBetter > numBetter) {
numBetter = hereBetter;
ind = i;
}
// if (numBetter == randNumBetter) break;
}
set<int> candidates;
for (int i=0; i<ind; i++) candidates.insert(i);
int pos = ind;
while (true) {
int remaining = numBetter-(int)candidates.size();
int l = max(pos+1, (*prev(BSstuff.lower_bound({-(remaining-1), -1e9}))).second);
int r = min(n-1, (*BSstuff.lower_bound({-(remaining-1), -1e9})).second);
// cerr << l << " " << r << "\n";
// return 0;
// 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);
}
