// ZERO INDEXING
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
int n;
map<int, pii> rsp;
pii qry(int i) {
if (rsp.count(i)) return rsp[i];
vec<sig> ans = ask(i);
rsp[i] = {ans[0], ans[1]};
return rsp[i];
}
int gd;
void gd_cmp() {
for (int i = 0; i < min(500ll, n); i++)
gd = max(gd, qry(i).fir + qry(i).sec);
}
vec<int> lst;
int cnt(int x) {
int ans = 0;
for (int y : lst) ans += (y <= x);
return ans;
}
int srch(vec<int>& rm) {
int lw = 0, hg = rm.size() - 1;
while (lw < hg) {
int md = (lw + hg) / 2;
if (qry(rm[md]).fir + qry(rm[md]).sec != gd) return md;
if (qry(rm[md]).fir - cnt(rm[md])) hg = md - 1;
else lw = md + 1;
}
return lw;
}
void lst_cmp() {
vec<int> rm;
for (int i = 0; i < n; i++) rm.push_back(i);
for (int x = 0; x < gd; x++) {
int i = srch(rm);
lst.push_back(rm[i]);
rm.erase(rm.begin() + i);
}
}
int ans_cmp() {
for (int i : lst)
if (qry(i).fir + qry(i).sec == 0) return i;
assert(false); return -1;
}
sig find_best(sig _n) {
n = _n;
gd_cmp();
lst_cmp();
int ans = ans_cmp();
return ans;
}
