#include "prize.h"
using namespace std;
#include <bits/stdc++.h>
int numBetter = 0;
set<int> candidates;
map<int, vector<int>> rem;
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);
return rem[pos];
}
int find_best(int n) {
candidates.clear();
sol=-1;
rem.clear();
numBetter=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;
}
}
set<pair<int, vector<int>>> s;
int ahhhh = 0;
while (getNumBetter(myAsk(ahhhh)) < numBetter) {
candidates.insert(ahhhh);
ahhhh++;
}
s.insert({ahhhh, myAsk(ahhhh)});
ahhhh = n-1;
while (getNumBetter(myAsk(ahhhh)) < numBetter) {
candidates.insert(ahhhh);
ahhhh--;
}
s.insert({ahhhh, myAsk(ahhhh)});
for (int i = 0; i<100; i++) {
auto p = s.begin();
while (next(p) != s.end()) {
if((*p).second[0] != (*next(p)).second[0]) {
int m = ((*p).first + (*next(p)).first)/2;
int inc = rand()%2;
while (getNumBetter(myAsk(m)) < numBetter) {
candidates.insert(m);
m+=1-2*inc;
}
s.insert({m, myAsk(m)});
}
p++;
}
}
for (int i: candidates) {
if (getNumBetter(myAsk(i)) == 0) return i;
}
assert(0);
}
