#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];
}
void gen(int rl, int rr) {
if (rl == rr) {candidates.insert(rl); return;}
int m = (rl + rr)/2;
auto res = myAsk(m);
auto left = myAsk(rl);
auto right = myAsk(rr);
if (res[0] != left[0] || getNumBetter(res)<numBetter || getNumBetter(left)<numBetter) gen(rl, m);
if (res[1] != right[1] || getNumBetter(res)<numBetter || getNumBetter(right)<numBetter) gen(m+1, rr);
}
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;
}
}
gen(0, n-1);
for (int i: candidates) {
if (getNumBetter(myAsk(i)) == 0) return i;
}
assert(0);
}
