#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 {
vector<int> inds;
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) {
inds.push_back(i);
i++;
continue;
}
const int T = 700;
int j = FIND_LARGEST(i, min(n - 1, i + T), [&](int j) { return count(j) == count(i); });
// if (j > i + T)
// cout << "Nah." << endl;
// if (j > i + T + 1)
// j = FIND_LARGEST(i + T + 1, n - 1, [&](int j) { return count(j) == count(i); });
// int j = FIND_LARGEST(i, n - 1, [&](int j) { return count(j) == count(i); });
cnt++;
i = j + 1;
}
// cout << "cnt = " << cnt << endl;
}
int find_best(int _n) {
n = _n;
cnt.assign(n, vector<int>());
try {
MAX_S = count_both(0);
extract_inds();
}
catch (int i) {
return i;
}
return -1;
}
}
int find_best(int n) {
return SUB2A::find_best(n);
}
