#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);
return a[0] + a[1];
}
void extract_inds() {
for (int i = 0; i < n; ) {
if (count_both(i) < MAX_S) {
inds.push_back(i);
i++;
continue;
}
int j = FIND_LARGEST(i, n - 1, [&](int j) { return count(j) == count(i); });
i = j + 1;
}
}
int find_best(int _n) {
n = _n;
cnt.assign(n, vector<int>());
MAX_S = 0;
for (int i = 0; i < n and i < 400; i++) {
int s = count_both(i);
if (s == 0)
return i;
maximise(MAX_S, s);
}
extract_inds();
for (int i : inds)
if (count_both(i) == 0)
return i;
return -1;
}
}
namespace SUB2B {
const int MAX_BLOCK = 100;
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 l, int r) {
while (l <= r and count_both(l) < MAX_S)
inds.push_back(l++);
while (l <= r and count_both(r) < MAX_S)
inds.push_back(r--);
if (l > r)
return;
if (count(l) == count(r))
return;
for (int i = l; i <= r; ) {
if (count_both(i) < MAX_S) {
inds.push_back(i);
i++;
continue;
}
int j = FIND_LARGEST(i, r, [&](int j) { return count(j) == count(i); });
i = j + 1;
}
}
int find_best(int _n) {
n = _n;
cnt.assign(n, vector<int>());
try {
MAX_S = 0;
for (int i = 0; i < n and i < 400; i++) {
int s = count_both(i);
maximise(MAX_S, s);
}
vector<pair<int, int>> ranges;
for (int l = 0, r = MAX_BLOCK; l < n; l += MAX_BLOCK, r += MAX_BLOCK) {
minimise(r, n - 1);
ranges.emplace_back(l, r);
}
shuffle(ranges.begin(), ranges.end(), mt19937(999));
for (const auto &range : ranges) {
int l, r;
tie(l, r) = range;
extract_inds(l, r);
}
for (int i : inds)
if (count_both(i) == 0)
return i;
}
catch (int i) {
return i;
}
return -1;
}
}
int find_best(int n) {
return SUB2B::find_best(n);
}
