#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 = 1;
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)->int {
// query(L), query(R);
// adjust(L, R);
int tl = query(R).f - query(L).f;
int m = 0; rep(i, L, START_QUERIES) if (group[i] != largest) m++;
if (L >= R || tl <= 0) return -1;
set<int> skip;
vi order;
for (int i = query(L).f+m; i < query(R).f; i++) order.pb(i);
shuffle(all(order), rng);
for (auto i : order) {
// for (int i = query(L).f+m; i < query(R).f; i++) {
// for (int i = query(R).f-1; i >= query(L).f+m; i--) {
if (skip.count(i)) continue;
int lo = L, hi = R+1;
while (lo < hi) {
int mid = lo + (hi-lo) / 2;
query(mid); if (group[mid] > largest) return mid;
int j = mid, k = mid;
while (j > 0 && group[j] < largest) {
query(--j); if (group[j] > largest) return j;
}
while (k < n-1 && group[k] < largest){
query(++k); if (group[k] > largest) return k;
}
if (query(j).f > i) hi = j;
else {
int base = query(j).f;
bool did = false;
rep(p, j+1, k) {
int v = base + (p-j);
if (v > i) {did = true; hi = lo = p; break;}
}
if (!did) lo = k+1;
}
}
if (lo > 0) query(lo-1);
if (group[lo-1] > largest) return lo-1;
}
return -1;
};
int v = search_range(search_range, 0, n-1);
while (v != -1) {
largest = group[v];
int L = 0, R = n-1;
adjust(L, R);
v = search_range(search_range, L, R);
}
return buckets[0][0];
}
