#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];
}
int sol = -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});
}
if (getNumBetter(rem[pos]) == 0) sol = pos;
return rem[pos];
}
int find_best(int n) {
sol=-1;
rem.clear();
numBetter=0;
BSstuff.clear();
BSstuff.insert({-1e9, 0});
BSstuff.insert({1e9, n-1});
int ind = 0;
for (int i = 0; i<min(n, 474); i++) {
int hereBetter = getNumBetter(myAsk(i));
if (sol != -1) return sol;
if (hereBetter > numBetter) {
numBetter = hereBetter;
ind = i;
}
}
set<int> candidates;
for (int i=0; i<ind; i++) candidates.insert(i);
int pos = ind;
for (int i = ind; i<min(n, 474); i++) {
if(getNumBetter(myAsk(i))==numBetter) continue;
candidates.insert(i);
pos = i+1;
}
while(pos<n&&getNumBetter(myAsk(pos))!=numBetter) {
candidates.insert(pos);
pos++;
}
for (int j = pos; j<n; j+=1600) {
int miau = j;
while(miau<n&&getNumBetter(myAsk(miau))!=numBetter) miau++;
}
while (true) {
if ((int)candidates.size() == numBetter) break;
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);
while (l<r) {
int m = (l+r)/2;
vector<int> ans = myAsk(m);
if (sol != -1) return sol;
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) {
// if (sol != -1) return sol;
candidates.insert(pos);
// pos++;
// }
if ((int)candidates.size() == numBetter) break;
}
for (int i: candidates) {
if (getNumBetter(myAsk(i)) == 0) return i;
}
assert(0);
}
