#include "prize.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
int find_best(int n) {
int mx = 0, worst;
vector<int> worst_res;
// Finds the first lollipop
for (worst = 0; worst < min(n, 500); worst++) {
vector<int> res = ask(worst);
if (res[0] + res[1] >= 22) {
worst_res = res;
worst++;
break;
} else if (res[0] + res[1] > mx) {
mx = res[0] + res[1];
worst_res = res;
} else if (res[0] + res[1] == 0) return worst;
}
// Binary searches for the other prizes
indexed_set remaining;
FOR(i, worst, n) remaining.insert(i);
while (remaining.size()) {
int l = 0, r = remaining.size() - 1;
while (l != r) {
int mid = (l + r + 1) / 2;
int pos = *remaining.find_by_order(mid);
vector<int> res = ask(pos);
if (res[0] + res[1] == 0) return pos;
else if (res[0] + res[1] == worst_res[0] + worst_res[1]) {
if (res[1] == worst_res[1]) {
while (*remaining.begin() != pos) remaining.erase(remaining.begin());
remaining.erase(remaining.begin());
break;
} else r = mid - 1;
} else {
remaining.erase(pos);
break;
}
}
}
return -1;
}
