#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;
int b = 473, cnt = 0;
for (int i = 0; i < n; i += b) {
auto res = query(i);
mxc = max(mxc,res[0]+res[1]);
++cnt;
}
if (cnt) for (int i = 1; i <= min(n,473)-cnt; ++i) {
auto res = query(i);
mxc = max(mxc,res[0]+res[1]);
++cnt;
}
int pre = 0;
for (int i = 0; i < n;) {
auto res = query(i);
int c = res[0]+res[1];
if (c == 0) return i;
pre += (c == mxc);
auto it = cache.upper_bound(i);
while (it != cache.end()) {
auto y = it->second;
if (y[0]+y[1] == mxc && y[0] == i+1-pre) ++it;
else break;
}
int lo = prev(it)->first, hi = (it == cache.end() ? n : it->first);
while (hi-lo > 1) {
int mid = (lo+hi)/2;
auto y = query(mid);
if (y[0]+y[1] == mxc && y[0] == i+1-pre) lo = mid;
else hi = mid;
}
pre += hi-i-1;
i = hi;
}
assert(false);
return 0;
}
