#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
if (x > y) { x = y; return true; }
return false;
}
template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
if (x < y) { x = y; return true; }
return false;
}
template <class F>
int FIND_SMALLEST(int l, int r, F f) {
int res = r + 1;
while (l <= r) {
int m = (l + r) / 2;
if (f(m)) res = m, r = m - 1;
else l = m + 1;
}
return res;
}
template <class F>
int FIND_LARGEST(int l, int r, F f) {
int res = l - 1;
while (l <= r) {
int m = (l + r) / 2;
if (f(m)) res = m, l = m + 1;
else r = m - 1;
}
return res;
}
namespace SUB1 {
int find_best(int n) {
int l = 0, r = n - 1;
while (l <= r) {
int m = (l + r) >> 1;
auto cnt = ask(m);
if (cnt[0] == cnt[1])
return m;
if (cnt[0] < cnt[1])
l = m + 1;
else
r = m - 1;
}
return -1;
}
}
namespace SUB2A {
int n, MAX_S;
vector<vector<int>> cnt;
vector<int>& count(int i) {
if (cnt[i].empty())
cnt[i] = ask(i);
return cnt[i];
}
int count_both(int i) {
auto &a = count(i);
int res = a[0] + a[1];
if (res == 0)
throw i;
return res;
}
void extract_inds() {
int cnt = 0;
for (int i = 0; i < n; ) {
if (count_both(i) < MAX_S) {
i++;
continue;
}
int k = FIND_LARGEST(0, log2(n - i) + 1, [&](int k) {
return i + (1 << k) < n and count(i + (1 << k)) == count(i);
});
// cerr << "i = " << i << " -> k = " << k << endl;
while (k >= 0) {
if (i + (1 << k) < n and count(i + (1 << k)) == count(i))
i += 1 << k;
k--;
}
cnt++;
i++;
}
// cout << "cnt = " << cnt << endl;
}
int find_best(int _n) {
n = _n;
cnt.assign(n, vector<int>());
try {
MAX_S = 0;
for (int i = 0; i < 3 and i < n; i++)
maximise(MAX_S, count_both(i));
extract_inds();
}
catch (int i) {
return i;
}
return -1;
}
}
int find_best(int n) {
return SUB2A::find_best(n);
}
