#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int mx_cnt;
}
int solve(int l, int r) {
if (l > r)
return -1;
if (l == r) {
auto a = ask(l);
if (a[0] + a[1] == 0)
return l;
}
auto al = ask(l);
auto ar = ask(r);
if (al[0] + al[1] == mx_cnt && ar[0] + ar[1] == mx_cnt && al[0] == ar[0])
return -1;
int m = (l + r) / 2;
return max(solve(l, m), solve(m + 1, r));
}
int find_best(int n) {
mx_cnt = 0;
for (int i = 0; i < min(n, 500); ++i) {
auto a = ask(i);
if (a[0] + a[1] == 0)
return i;
mx_cnt = max(mx_cnt, a[0] + a[1]);
}
return solve(0, n - 1);
}
