#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
const int mxN = 2e5+5;
const int mxQ = 10000;
int n, q = 0;
map<int,vector<int>> cache;
vector<int> query(int i) {
//TRACE("QUERY" _ i);
assert(i >= 0 && i < n);
if (cache.count(i)) return cache[i];
assert(++q <= mxQ);
return cache[i] = ask(i);
}
int find_best(int _n) {
n = _n;
int mxc = 0;
for (int i = 0; i < min(n,473); ++i) {
auto res = query(i);
mxc = max(mxc,res[0]+res[1]);
}
for (int i = 0; i < n;) {
auto res = query(i);
int c = res[0]+res[1];
if (c == 0) return i;
if (c == mxc) {
int lo = i, hi = n;
while (hi-lo > 1) {
int mid = (lo+hi)/2;
auto y = query(mid);
if (y[0] == res[0] && y[1] == res[1]) lo = mid;
else hi = mid;
}
i = hi;
} else ++i;
}
assert(false);
return 0;
}
