#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
if (x < y) { x = y; return true; }
return false;
}
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 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(int l, int r) {
// cout << "extract " << l << " " << r << endl;
if (l > r)
return;
if (count_both(l) < MAX_S) {
inds.push_back(l);
extract(l + 1, r);
return;
}
if (count_both(r) < MAX_S) {
inds.push_back(r);
extract(l, r - 1);
return;
}
if (l == r)
return;
int m = (l + r) >> 1;
if (count_both(m) < MAX_S) {
inds.push_back(m);
extract(l, m - 1);
extract(m + 1, r);
}
else {
extract(l, m - 1);
extract(m + 1, r);
}
}
int find_best(int n) {
cnt.assign(n, vector<int>());
MAX_S = 0;
for (int i = 0; i < n and i < 1000; i++) {
int s = count_both(i);
if (s == 0)
return i;
maximise(MAX_S, s);
}
// cout << "MAX_S = " << MAX_S << endl;
extract(0, n - 1);
for (int i : inds)
if (count_both(i) == 0)
return i;
return -1;
}
}
int find_best(int n) {
return SUB2A::find_best(n);
}
