#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > val;
vector<int> query(int i) {
if(val[i][0] == -1) return val[i] = ask(i);
return val[i];
}
int find_best(int n) {
val = vector<vector<int> >(n, vector<int>(2, -1));
int idx = -1;
vector<int> vec(2);
for(int i = 0; i < min(n, 480); i++) {
vector<int> now = query(i);
if(now[0] + now[1] == 0) return i;
if(now[0] + now[1] > vec[0] + vec[1])
vec = now, idx = i;
}
bool bad = true;
while(1) {
if(bad) {
int l = idx + 1, r = n - 1;
while(l < r) {
int mid = (l + r) >> 1;
vector<int> now = query(mid);
if(make_pair(vec[0], vec[1]) != make_pair(now[0], now[1]))
r = mid;
else l = mid + 1;
}
idx = r, bad = false;
} else {
vector<int> now = query(idx);
if(now[0] + now[1] == 0) return idx;
now = query(++idx);
if(now[0] + now[1] == vec[0] + vec[1])
bad = true, vec = now;
}
}
return 0;
}
