#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];
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
set<int> special;
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) {
special.insert(l);
l ++;
}
while (l <= r and sum(r) != total) {
special.insert(r);
r --;
}
// cout << l << " " << r << " range\n";
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 (special.count(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;
for (int j:special) if (l <= j and j <= mid) sum --;
if (sum > 0) high = mid-1;
else low = mid+1;
} else {
special.insert(mid);
found = 1;
break;
}
}
if (!found) break;
}
}
for (int i:special) if (sum(i) == 0) return i-1;
assert(0);
}
