#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
int solve(int low, int upp, int less, int more, int large) {
if (less + more == large) return 0;
int mid = (low + upp) / 2;
auto a = ask(mid);
int tot = a[0] + a[1];
if (tot == 0) return mid;
if (low == upp) return 0;
int res = 0;
if (tot == large) {
if (low < mid) res += solve(low, mid - 1, less, a[1], large);
if (mid < upp) res += solve(mid + 1, upp, a[0], more, large);
}
else {
int mdx = mid;
while (mdx++ < upp && tot < large) {
a = ask(mdx);
tot = a[0] + a[1];
if (tot == 0) return mdx;
}
if (tot == large) {
if (low < mid) res += solve(low, mid - 1, less, a[1] + mdx - mid, large);
if (mdx < upp) res += solve(mdx + 1, upp, a[0], more, large);
}
else if (low < mid) res += solve(low, mid - 1, less, more + mdx - mid, large);
}
return res;
}
int find_best(int n) {
if (n < 5000) {
for (int i = 0; i < n; ++i) {
auto a = ask(i);
if (a[0] + a[1] == 0) return i;
}
}
int large = 0;
vector<int> val(450);
for (int i = 0; i < 450; ++i) {
auto a = ask(i);
val[i] = a[0] + a[1];
if (val[i] == 0) return i;
large = max(large, val[i]);
}
int found = 0;
for (int a : val) if (a != large) found++;
return solve(450, n - 1, found, 0, large);
}
