#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
mt19937 rng((long long) (new char));
int rn(int l, int r) {
return l + rng() % (r - l + 1);
}
int cnt;
int rep(int l, int r, int q) {
assert(q >= 0);
if (l > r || q == 0) {
return 0;
}
int i = rn(l, r);
vector<int> v = ask(i); cnt++;
q--;
if (v[0] == 0 && v[1] == 0) {
return i;
}
if (v[0] == 0) {
return rep(i + 1, r, q);
}
if (v[1] == 0) {
return rep(l, i - 1, q);
}
/// cnt(0) / cnt(1) = v[0] / v[1]
/// cnt(0) + cnt(1) = q
int c0 = (long long) v[0] * q / (v[0] + v[1]);
int c1 = q - c0;
int x = rep(l, i - 1, c0);
if (x) {
return x;
} else {
return rep(i + 1, r, c1);
}
}
int find_best(int n) {
return rep(0, n - 1, 9000 + 1000 - 8);
}
