#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);
if (res[0]+res[1] == 0) throw 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 is_trash(int i) {
auto [ca, cb] = Ask(i);
return ca+cb == lowest_rank;
}
bool weirdo[maxn];
void find_all_weirdos(int l, int r, int cnt, int bl, int br) {
for (;;) {
if (!cnt || l>r) return;
if (vis[l]) {
if (!is_trash(l)) { weirdo[l] = true; --cnt; ++bl; }
++l; continue;
}
if (vis[r]) {
if (!is_trash(r)) { weirdo[r] = true; --cnt; ++br; }
--r; continue;
}
break;
}
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) {
try {
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);
int last_trash = -1, last_ca = 0;
for (int i=0; i<n; ++i) if (vis[i]) {
auto [ca, cb] = cache[i];
if (is_trash(i)) {
if (last_ca == ca) {
for (int j=last_trash+1; j<i; ++j) {
vis[j] = true;
cache[j] = cache[i];
}
} else {
find_all_weirdos(last_trash, i-1, ca-last_ca, last_ca, lowest_rank-ca);
}
last_trash = i;
last_ca = ca;
}
}
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;
} catch (int i) { return i; }
}
