#include "prize.h"
#define K 500
using namespace std;
typedef vector<int> vi;
int max(int a, int b) { return a > b ? a : b; }
int lollipop;
int solve(int l, int r, int l_, int r_) {
int m, i;
if (l_ == r_)
return -1;
m = (l + r) / 2;
for (i = m; i < r; i++) {
vi a = ask(i);
if (a[0] + a[1] == 0)
return i;
if (a[0] + a[1] == lollipop) {
int i_;
if ((i_ = solve(l, m, l_, a[0] - (i - m))) != -1)
return i_;
return solve(i + 1, r, a[0], r_);
}
}
for (i = m - 1; i >= l; i--) {
vi a = ask(i);
if (a[0] + a[1] == 0)
return i;
if (a[0] + a[1] == lollipop)
return solve(l, i, l_, a[0]);
}
return -1;
}
int find_best(int n) {
int i;
for (i = 0; i < n && i <= K; i++) {
vi a = ask(i);
if (a[0] + a[1] == 0)
return i;
lollipop = max(lollipop, a[0] + a[1]);
if (lollipop > 100)
return solve(i + 1, n, i + 1, lollipop);
}
return solve(0, n, 0, lollipop);
}
