#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rd(time(0));
int K = 1000; // block size
int N;
pair<int, int> cache[200005];
int nodes[800005];
void upd(int n, int l, int r, int p) {
if (l == r) {
nodes[n] = 1;
return;
}
int mid = (l+r)/2;
if (p <= mid) upd(2*n, l, mid, p);
else upd(2*n+1, mid+1, r, p);
nodes[n] = nodes[2*n] + nodes[2*n+1];
}
int query(int n, int l, int r, int ql, int qr) {
if (l > qr or r < ql) return 0;
if (ql <= l and r <= qr) return nodes[n];
int mid = (l+r)/2;
return query(2*n, l, mid, ql, qr) + query(2*n+1, mid+1, r, ql, qr);
}
pair<int, int> query(int i) {
if (cache[i].first != -1) return cache[i];
vector<int> v = ask(i-1);
return cache[i] = make_pair(v[0], v[1]);
}
int sum(int i) {
auto [x, y] = query(i);
return x+y;
}
int find_best(int n) {
N = n;
for (int i = 1; i <= N; i ++) cache[i] = {-1, -1};
// rng 50 times to find the max
int total = 0;
for (int t = 0; t < 50; t ++) total = max(total, sum(rd()%N+1));
// consider each block
for (int i = 1; i <= N; i += K) {
// i -> min(N, i+K-1)
int l = i, r = min(N, i+K-1);
while (l <= r and sum(l) != total) {
upd(1, 1, N, l);
l ++;
}
while (l <= r and sum(r) != total) {
upd(1, 1, N, l);
r --;
}
if (l > r) continue;
auto [a1, b1] = query(l);
// keep binary searching
while (true) {
int low = l, high = r;
bool found = 0;
while (high > low) {
int mid = (low + high)/2;
int old = mid;
while (query(1, 1, N, mid, mid)) mid ++;
if (mid > high) {
high = old-1;
continue;
}
auto [x, y] = query(mid);
if (x+y == total) {
// subtract the special things between [l, mid]
int sum = x - a1 - query(1, 1, N, l, mid);
if (sum > 0) high = old-1;
else low = mid+1;
} else {
upd(1, 1, N, mid);
found = 1;
break;
}
}
if (sum(low) != total) {
upd(1, 1, N, low);
found = 1;
}
if (!found) break;
}
}
for (int i = 1; i <= N; i ++) if (query(1, 1, N, i, i) and sum(i) == 0) return i-1;
assert(0);
}
