#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 size(pi x) {
return x.f + x.s;
}
vi group;
map<int, pi> cache;
pi query(int i) {
if (cache.count(i)) return cache[i];
vi res = ask(i); pi ans = {res[0], res[1]};
group[i] = size(ans);
return cache[i] = ans;
}
int find_best(int n) {
group.assign(n, -1);
query(0); int largest = group[0];
auto search_range = [&](auto &&self, int L, int R)->int {
int tl = query(R).f - query(L).f;
if (L >= R || tl <= 0) return -1;
for (int i = query(L).f; i < query(R).f; i++) {
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;
}
if (query(j).f > i) {
hi = j;
} else {
while (k < n-1 && group[k] < largest){
query(++k); if (group[k] > largest) return k;
}
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 = 0;
while (v != -1) {
largest = group[v];
int L = 0, R = n-1;
while (L < R && size(query(L)) != largest) L++;
while (R > L && size(query(R)) != largest) R--;
v = search_range(search_range, L, R);
}
int ans = 0; while (ans < n && group[ans] != 0) ans++;
return ans;
}
