#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
const int B = 480;
vector<int> arr[N];
vector<int> ASK(int p) {
if (arr[p].empty())
arr[p] = ask(p);
return arr[p];
}
int sum(int i) {
return ASK(i)[0] + ASK(i)[1];
}
int find_best(int n) {
int val = sum(0);
for (int i = 0; i < min(n, B); i++) {
if (!sum(i)) return i;
val = max(val, sum(i));
}
int cnt = 0;
for (int i = 0; i < B; i++) {
cnt += (sum(i) < val);
}
for (int it = B; it < n; it += B) {
int rb = min(it + B, n);
if (sum(rb-1) == val && arr[rb-1][0] == cnt)
continue;
int i = it;
while (i < rb) {
while (i < rb && sum(i) < val) {
if (!sum(i))
return i;
i++;
cnt++;
}
int l = i, r = rb;
while (r - l > 1) {
int mid = (l + r) / 2;
if (ASK(mid) == ASK(i))
l = mid;
else {
if (!sum(mid))
return mid;
r = mid;
}
}
i = r;
}
}
return 0;
}
