#include "prize.h"
#include <utility>
using namespace std;
using pp=pair<int,int>;
const int maxn = int(2e5) + 10;
pp cache[maxn];
bool vis[maxn];
pp Ask(int i) {
if (vis[i]) return cache[i];
vis[i] = true;
vector<int> res = ask(i);
return cache[i] = {res[0], res[1]};
}
int lowest_rank;
int _get_lowest_rank(int n) {
int mx = 0, step=n/500;
for (int i=0; i<500; ++i) {
auto [a, b] = Ask(i*step);
mx = max(mx, a+b);
}
return mx;
}
bool weirdo[maxn];
void find_all_weirdos(int l, int r, int cnt, int bl, int br) {
if (!cnt || l>r) return;
if (r-l+1 == cnt) {
for (int i=l; i<=r; ++i) weirdo[i] = true;
return;
}
int md = (l+r)/2;
for (int i=md; l<=i; --i) {
auto [ca, cb] = Ask(i);
if (ca+cb == lowest_rank) {
find_all_weirdos(l, i-1, ca-bl, bl, lowest_rank-ca);
break;
} else {
weirdo[i] = true;
}
}
for (int i=md; i<=r; ++i) {
auto [ca, cb] = Ask(i);
if (ca+cb == lowest_rank) {
find_all_weirdos(i+1, r, cb-br, lowest_rank-cb, br);
break;
} else {
weirdo[i] = true;
}
}
}
int find_best(int n) {
if (n <= 5000) {
for (int i=0; i<n; ++i) {
auto [a, b] = Ask(i);
if (a+b == 0) return i;
}
return -1;
}
lowest_rank = _get_lowest_rank(n);
find_all_weirdos(0, n-1, lowest_rank, 0, 0);
for (int i=0; i<n; ++i) if (weirdo[i]) {
auto [a, b] = Ask(i);
if (a+b == 0) return i;
}
return -1;
}
