#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int mx_cnt;
}
int solve(int l, int r, vector<int> h, int f) {
if (l > r)
return -1;
if (l == r) {
auto a = f == -1 ? ask(l) : h;
if (a[0] + a[1] == 0)
return l;
return -1;
}
auto al = f == 0 ? h : ask(l);
auto ar = f == 1 ? h : ask(r);
if (al[0] + al[1] == 0)
return l;
if (ar[0] + ar[1] == 0)
return 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, al, 0), solve(m + 1, r, ar, 1));
}
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, {}, -1);
}
