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