#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<int, int>;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int((x).size()))
#define pb push_back
#define f first
#define s second
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rev(i, a, b) for (int i = (a); i >= (b); i--)
template<class T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<class T> bool chmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}
const int INF = 1e9 + 5;
const ll LINF = 4e18;
#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << (x) << endl;
#else
#define dbg(x)
#endif
int n;
int size(pi x) {
return x.f + x.s;
}
int T = 0, Q = 0;
map<int, pi> cache;
map<int, vi> buckets;
vi group;
pi query(int i) {
T++;
if (cache.count(i)) return cache[i];
Q++;
vi res = ask(i);
pi ans = {res[0], res[1]};
group[i] = size(ans); buckets[group[i]].push_back(i);
return cache[i] = ans;
}
bool is_diamond(pi x) {
return x.f == x.s && x.s == 0;
}
bool has_found() {
return buckets.count(0) && buckets[0].size() > 0;
}
int find_best(int N) {
n = N; mt19937 rng(-1);
vi order(n); iota(all(order), 0); shuffle(all(order), rng);
group.assign(n, -1);
if (n <= 5000) {
rep(i, 0, n) {
query(i);
}
return has_found() ? buckets[0][0] : -1;
}
const int START_QUERIES = 550;
rep(i, 0, START_QUERIES) query(i);
int largest = *max_element(bg(group), bg(group) + START_QUERIES);
auto adjust = [&](int &L, int &R)->void {
while (L < R && (group[L] != largest || group[R] != largest)) {
while (L < R && group[L] != largest) {
L++; query(L);
}
while (R > L && group[R] != largest) {
R--; query(R);
}
}
};
auto search_range = [&](auto &&self, int L, int R)->void {
query(L), query(R);
adjust(L, R);
int tl = query(R).f - query(L).f, i = query(L).f;
if (L >= R || tl <= 0) return;
int lo = L, hi = R+1;
while (lo < hi) {
int mid = lo + (hi-lo) / 2;
query(mid);
int j = mid, k = mid;
while (j > 0 && group[j] < largest) query(--j);
while (k < n-1 && group[k] < largest) query(++k);
if (j < mid || k > mid) {
int base = query(j).f;
if (base > i) {hi = j; continue;}
bool did = false;
rep(p, j+1, k) {
int v = base + (p-j);
if (v > i) {did = true; hi = p; break;}
}
if (!did) lo = k+1;
} else {
if (query(mid).f > i) hi = mid;
else lo = mid+1;
}
}
if (lo > 0) query(lo-1);
self(self, lo, R);
};
search_range(search_range, 0, n-1);
auto found_size = [&]() {
int x = 0;
for (auto &[s, t] : buckets) {
if (s != largest) x += sz(t);
}
return x;
};
// cout << sz(buckets) << "\n";
// for (auto &[s, t] : buckets) {
// cout << "found " << sz(t) << " elements with size " << s << "\n";
// }
while (found_size() < largest) {
for (auto &[s, t] : buckets) {
if (s == largest) continue;
sort(all(t));
rep(i, 0, sz(t) - 1) {
// if (query(t[i+1]).f - query(t[i]).f <= 0) continue;
search_range(search_range, t[i]+1, t[i+1]-1);
}
}
}
if (has_found()) return buckets[0][0];
return -1;
}
