#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int b = 300;
map<int, pair<int, int>> cache;
int big, n_global, ans = -1;
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int n = 0) : n(n), bit(n + 1, 0) {}
void add(int i, int v) {
for (++i; i <= n; i += i & -i) bit[i] += v;
}
int sum(int i) {
if (i < 0) return 0;
int r = 0;
for (++i; i > 0; i -= i & -i) r += bit[i];
return r;
}
int range_sum(int l, int r) {
if (l > r) return 0;
return sum(r) - sum(l - 1);
}
};
Fenwick removed_small;
pair<int, int> query(int x) {
if (cache.find(x) != cache.end()) return cache[x];
vector<int> q = ask(x);
cache[x] = {q[0], q[1]};
return cache[x];
}
int tot(int x) {
auto q = query(x);
return q.first + q.second;
}
bool diamond(int x) {
auto q = query(x);
return q.first == 0 && q.second == 0;
}
int left_count(int x) {
if (x == -1) return 0;
if (x == n_global) return big;
return query(x).first;
}
int alive_count(set<int> &inds, int l, int r) {
int res = 0;
auto it = inds.upper_bound(l);
while (it != inds.end() && *it < r) {
res++;
it++;
}
return res;
}
int kth_alive(set<int> &inds, int l, int r, int k) {
auto it = inds.upper_bound(l);
while (it != inds.end() && *it < r) {
if (k == 0) return *it;
k--;
it++;
}
assert(false);
}
bool scan_range(set<int> &inds, int l, int r) {
vector<int> v;
auto it = inds.upper_bound(l);
while (it != inds.end() && *it < r) {
v.push_back(*it);
it++;
}
for (int x : v) {
if (diamond(x)) {
ans = x;
return true;
}
if (tot(x) != big) {
inds.erase(x);
removed_small.add(x, 1);
}
}
return false;
}
bool solve_between(set<int> &inds, int l, int r, int cnt) {
while (cnt > 0) {
int len = alive_count(inds, l, r);
if (len == 0) return false;
if (len <= 1) {
return scan_range(inds, l, r);
}
int lg = 0;
while ((1LL << lg) < len) lg++;
if (len <= cnt * lg) {
return scan_range(inds, l, r);
}
int mid = kth_alive(inds, l, r, len / 2);
if (diamond(mid)) {
ans = mid;
return true;
}
if (tot(mid) != big) {
inds.erase(mid);
removed_small.add(mid, 1);
cnt--;
continue;
}
int lc = left_count(l);
int rc = left_count(r);
int mc = query(mid).first;
int left_removed = removed_small.range_sum(l + 1, mid - 1);
int right_removed = removed_small.range_sum(mid + 1, r - 1);
int left_cnt = mc - lc - left_removed;
int right_cnt = rc - mc - right_removed;
if (solve_between(inds, l, mid, left_cnt)) return true;
if (solve_between(inds, mid, r, right_cnt)) return true;
return false;
}
return false;
}
pair<bool, int> blksolve(pair<int, int> &blk) {
set<int> inds;
for (int i = blk.first + 1; i < blk.second; i++) inds.insert(i);
int cnt = left_count(blk.second) - left_count(blk.first);
cnt -= removed_small.range_sum(blk.first + 1, blk.second - 1);
bool ok = solve_between(inds, blk.first, blk.second, cnt);
return {ok, ans};
}
int find_best(int n) {
n_global = n;
removed_small = Fenwick(n);
vector<int> samples;
for (int i = 0; i < n; i += b) samples.push_back(i);
if (samples.back() != n - 1) samples.push_back(n - 1);
big = 0;
for (int x : samples) {
if (diamond(x)) return x;
big = max(big, tot(x));
}
big = max({big, tot(n / 2), tot(n / 3), tot(n / 5), tot(n / 7), tot(n / 9)});
for (auto &[x, q] : cache) {
if (q.first == 0 && q.second == 0) return x;
big = max(big, q.first + q.second);
}
vector<pair<int, int>> bad_segments;
for (int i = 0; i + 1 < (int)samples.size(); i++) {
int l = samples[i], r = samples[i + 1];
bool bad = false;
if (tot(l) != big) bad = true;
if (tot(r) != big) bad = true;
if (tot(l) == big && tot(r) == big && query(l).first != query(r).first) bad = true;
if (bad) bad_segments.push_back({i, i});
}
if (bad_segments.empty()) {
for (int i = 0; i < n; i++) {
if (diamond(i)) return i;
}
}
vector<pair<int, int>> merged;
for (auto seg : bad_segments) {
if (merged.empty() || seg.first > merged.back().second + 1) {
merged.push_back(seg);
} else {
merged.back().second = seg.second;
}
}
vector<pair<int, int>> blk;
for (auto [l, r] : merged) {
int left_anchor = (l == 0 ? -1 : samples[l - 1]);
int right_anchor = (r + 2 >= (int)samples.size() ? n : samples[r + 2]);
blk.push_back({left_anchor, right_anchor});
}
for (auto &x : blk) {
pair<bool, int> p = blksolve(x);
if (p.first) return p.second;
}
for (int i = 0; i < n; i++) {
if (diamond(i)) return i;
}
assert(false);
}
