#pragma GCC optimize ("O3")
#include "prize.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int up = 2e5 + 5;
int okay = 0;
vi cnt[up];
vi ASK(int i) {
if (cnt[i][0] != oo) return cnt[i];
else return ask(i);
}
void solve(int l, int r, int subL, int subR) {
if (l <= r) {
int mid = (l + r) >> 1;
vi a = ASK(mid);
if (a[0] + a[1] < okay) { /// not last type
int lmid = mid - 1, rmid = mid + 1;
cnt[mid] = a;
while (lmid >= l) {
a = ASK(lmid);
if (a[0] + a[1] < okay) {
cnt[lmid] = a;
--lmid;
} else {
break;
}
}
if (a[0] - subL > 0 && lmid > l) {
solve(l, lmid - 1, subL, a[1]);
}
while (rmid <= r) {
a = ASK(rmid);
if (a[0] + a[1] < okay) {
cnt[rmid] = a;
++rmid;
} else {
break;
}
}
if (a[1] - subR > 0 && rmid < r) {
solve(rmid + 1, r, a[0], subR);
}
} else { /// last type
if (a[0] - subL > 0) {
solve(l, mid - 1, subL, a[1]);
}
if (a[1] - subR > 0) {
solve(mid + 1, r, a[0], subR);
}
}
}
}
int find_best(int n) {
vi p(n);
for (int i = 0; i < n; ++i) {
p[i] = i;
cnt[i] = {oo, oo};
}
shuffle(all(p), rng);
for (int i = 0; i < n && i < 473; ++i) { /// type_cnt[1, 4, 21, 446, last] 1 + 4 + 21 + 446 = 472
cnt[p[i]] = ASK(p[i]);
okay = max(okay, cnt[p[i]][0] + cnt[p[i]][1]);
if (okay > 26) break; /// 1 + 4 + 21 = 26
}
solve(0, n - 1, 0, 0);
for (int i = 0; i < n; ++i) {
if (cnt[i][0] + cnt[i][1] == 0) return i;
}
}
