#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include "prize.h"
#include <set>
std::mt19937 rng(123);
std::vector<std::pair<int, int>> memo;
std::set<int> cand;
int queries = 0;
int answer = -1;
std::pair<int, int> query(int i) {
if (memo[i].first != -1) {
return memo[i];
}
queries++;
if (queries > 10000) {
assert(false);
assert((int) cand.size() >= 600);
}
auto aux = ask(i);
if (aux[0] == 0 && aux[1] == 0) {
answer = i;
}
return memo[i] = std::pair<int, int>{aux[0], aux[1]};
}
int total_less(int i) {
return query(i).first + query(i).second;
}
int countnonmax;
bool is_max(int i) {
if (total_less(i) == 0) {
answer = i;
}
return total_less(i) == countnonmax;
}
int find_best(int n) {
memo.resize(n, std::pair<int, int>{-1, -1});
if (n <= 5000) {
for (int i = 0; i < n; i++) {
if (total_less(i) == 0) {
return i;
}
}
}
auto get = [&](auto &self, int l, int r, int countLeft) { // countLeft = cate sunt bune in [0, l)
if (l == r) {
return l;
}
int mid = (l + r) / 2;
int p = mid;
while (p >= l && answer == -1 && !is_max(p)) {
cand.insert(p--);
}
if (answer != -1) {
return -1;
}
if (p < l) {
return l;
}
int st = query(p).first;
// std::cout << " ! " << l << ' ' << r << ' ' << p << ' ' << st << '\n';
if (st == countLeft) {
if (p != mid) { // stiu sigur ca p + 1 e bun
return p + 1;
} else { // siu ca in [l..mid] nu e niciunul bun
return self(self, mid + 1, r, st);
}
} else {
return self(self, l, p, countLeft);
}
};
int p1 = rng() % n;
int p2 = rng() % n;
int p3 = rng() % n;
int p4 = rng() % n;
countnonmax = std::max({total_less(p1), total_less(p2), total_less(p3), total_less(p4)});
int l = 0, r = n - 1;
while (!is_max(l)) {
cand.insert(l++);
}
while (!is_max(r)) {
cand.insert(r--);
}
// stiu ca l si r sunt max
while (query(r).first > query(l).first) {
int p = get(get, l + 1, r - 1, query(l).first);
if (p == -1) {
return answer;
}
// std::cout << " ? " << l << ' ' << r << ' ' << p << '\n';
while (!is_max(p) && answer == -1) {
cand.insert(p++);
}
if (answer != -1) {
return answer;
}
l = p;
}
for (int x : cand) {
if (total_less(x) == 0) {
return x;
}
}
}
