#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
vector<int> total(500);
for (int i = 0; i < min(n, 500); i++) {
vector<int> cnt = ask(i);
total[i] = cnt[0] + cnt[1];
if (total[i] == 0) return i;
}
int mx = 0;
for (int i = 0; i < min(n, 500); i++) {
mx = max(mx, total[i]);
}
int luck = 0;
for (int i = 0; i < min(n, 500); i++) {
if (total[i] != mx) luck++;
}
int leftBorder = 500;
while (true) {
int l = leftBorder, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
vector<int> cnt = ask(mid);
int total = cnt[0] + cnt[1];
if (total == 0) return mid;
if (total == mx && cnt[0] == luck) {
l = mid + 1;
}
else {
r = mid;
}
}
vector<int> cnt = ask(l);
int total = cnt[0] + cnt[1];
if (total == 0) return l;
leftBorder = l + 1;
luck++;
}
}
