#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include "prize.h"
std::mt19937 rng(123);
std::vector<std::pair<int, int>> memo;
int queries = 0;
std::pair<int, int> query(int i) {
if (memo[i].first != -1) {
return memo[i];
}
queries++;
assert(queries <= 10000);
auto aux = ask(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) {
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;
}
}
}
std::vector<int> cand;
auto get = [&](auto &self, int l, int r, int count) -> void {
if (count == 0 || l > r) {
return;
}
if (r - l <= 2) {
for (int i = l; i < r && count; i++) {
if (!is_max(i)) {
cand.push_back(i);
count--;
}
}
if (count) {
cand.push_back(r);
}
return;
}
int mid = (l + r) / 2;
while (l <= r && !is_max(l)) {
cand.push_back(l++);
}
while (r >= l && !is_max(r)) {
cand.push_back(r--);
}
if (l > r) {
return;
}
int split_left = mid;
int split_right = mid;
while (split_left >= l && !is_max(split_left)) {
cand.push_back(split_left--);
}
while (split_right <= r && !is_max(split_right)) {
cand.push_back(split_right++);
}
std::pair<int, int> L, SL, SR, R;
if (l + 1 < split_left) {
L = query(l);
SL = query(split_left);
self(self, l + 1, split_left - 1, SL.first - L.first);
}
if (split_right + 1 < r) {
SR = query(split_right);
R = query(r);
self(self, split_right + 1, r - 1, R.first - SR.first);
}
return;
// int mid = l + rng() % (r - l + 1);
// if (is_max(mid)) {
// if (query(mid).first < countLeft) {
// countLeft = 0;
// countRight = 0;
// }
// self(self, l, mid - 1, total_less(mid) - countLeft - countRight, countLeft, query(mid).second - countRight);
// self(self, mid + 1, r, total_less(mid) - countLeft - countRight, query(mid).first - countLeft, countRight);
// } else {
// int st, dr;
// st = mid - query(mid).first;
// dr = n - mid - 1 - query(mid).second;
// self(self, l, mid - 1, );
// }
// return cand;
// int aux = mid;
// while (mid <= r && !is_max(mid)) {
// cand.push_back(mid);
// mid++;
// }
// int split_left = aux;
// int split_right = mid;
// self(self, l, split_left - 1, query(mid1).first);
};
int p1 = rng() % n;
int p2 = rng() % n;
int p3 = rng() % n;
countnonmax = std::max({total_less(p1), total_less(p2), total_less(p3)});
get(get, 0, n - 1, countnonmax);
std::sort(cand.begin(), cand.end());
cand.erase(std::unique(cand.begin(), cand.end()), cand.end());
for (int i = 0; i < (int) cand.size(); i++) {
if (total_less(cand[i]) == 0) {
return cand[i];
}
}
}
