#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
int find_best(int n) {
int worst = 0;
auto vec = ask(worst);
int exp = vec[0] + vec[1];
if (exp == 0) return 0;
for (int i = 1; i < min(500, n); i++) {
auto shit = ask(i);
if (shit[0] + shit[1] == 0) return i;
if (shit[0] + shit[1] > exp) {
exp = shit[0] + shit[1];
vec = shit;
worst = i;
}
}
vector<bool> blocked(n);
auto find_next = [&](int worst) -> int {
int best = -1;
deque<int> d;
for (int i = worst; i < n; i++) if (!blocked[i]) d.push_back(i);
while (!d.empty()) {
int mid = d.size() / 2;
auto shit = ask(d[mid]);
// cout << d[mid] << ' ' << shit[0] << ' ' << shit[1] << endl;
if (shit[0] + shit[1] == 0) return d[mid];
if (vec[0] + vec[1] != shit[0] + shit[1]) {
blocked[d[mid]] = true;
d.erase(d.begin() + mid);
continue;
}
if (vec == shit) {
best = d[mid];
for (int i = 0; i <= mid; i++) d.pop_front();
} else {
while (mid <= d.size()) d.pop_back();
}
}
assert(best != -1);
return best;
};
worst = find_next(worst);
vec = ask(worst);
// cout << worst << ' ' << vec[0] << ' ' << vec[1] << endl;
if (vec[0] + vec[1] == 0) return worst;
while (true) {
for (int i = worst + 1; i < n; i++) {
auto shit = ask(i);
if (shit[0] + shit[1] == 0) return i;
if (shit[0] + shit[1] == vec[0] + vec[1]) {
vec = shit;
worst = i;
break;
}
}
worst = find_next(worst);
vec = ask(worst);
if (vec[0] + vec[1] == 0) return worst;
}
// assert(false);
return -1;
}
