#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = (int) 2e5;
static bool mark[MAXN];
static vector <int> qry[MAXN];
static inline vector <int> myask(int pos) {
if(mark[pos] == 0) {
qry[pos] = ask(pos);
}
mark[pos] = 1;
return qry[pos];
}
static int solve(int l, int r, int numl, int numr, int mx) {
if(l > r) return -1;
int mid = (l + r) / 2;
int ll = mid, rr = mid;
while(ll >= l && myask(ll)[0] + myask(ll)[1] < mx) {
auto cur = myask(ll);
if(cur[0] + cur[1] == 0) return ll;
ll--;
}
while(rr <= r && myask(rr)[0] + myask(rr)[1] < mx) {
auto cur = myask(rr);
if(cur[0] + cur[1] == 0) return rr;
rr++;
}
auto x = myask(max(ll, l)), y = myask(min(rr, r));
int ans = -1;
if(x[0] - numl > 0) {
ans = max(ans, solve(l, ll - 1, numl, x[1], mx));
}
if(y[1] - numr > 0) {
ans = max(ans, solve(rr + 1, r, y[0], numr, mx));
}
return ans;
}
int find_best(int n) {
srand(time(NULL));
auto myrand = [&]() {
return (1LL * (1LL << 15) * rand() + rand()) % n;
};
vector <bool> vis(n);
int mx = 0;
for(int i = 0; i < min(n, 300); i++) {
int p = myrand();
while(vis[p]) { p = myrand(); }
vis[p] = 1;
auto cur = myask(p);
mx = max(mx, cur[0] + cur[1]);
}
return solve(0, n - 1, 0, 0, mx);
}
