#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 rep(int l, int r, int q) {
assert(q >= 0);
if (l > r || q == 0) {
return 0;
}
int m = (l + r) / 2;
int p1 = max(l, m - 5);
int p2 = min(r, m + 5);
if (q == 0) {
return 0;
}
q--;
vector<int> aprox = ask(m);
if (aprox[0] == 0 && aprox[1] == 0) {
return m;
}
for (int j = p1; j <= p2; j++) {
if (j != m) {
if (q == 0) {
return 0;
}
q--;
vector<int> v = ask(j);
if (v[0] == 0 && v[1] == 0) {
return j;
}
aprox[0] = min(aprox[0], v[0]);
aprox[1] = min(aprox[1], v[1]);
}
}
if (aprox[0] == 0) {
return rep(p2 + 1, r, q);
}
if (aprox[1] == 0) {
return rep(l, p1 - 1, q);
}
int c0 = (long long) aprox[0] * q / (aprox[0] + aprox[1]);
int c1 = q - c0;
int x = rep(l, p1 - 1, c0);
if (x) {
return x;
} else {
return rep(p2 + 1, r, c1);
}
}
int find_best(int n) {
return rep(0, n - 1, 9000 + 1000 - 8);
}
