#ifndef GRADER
#include "prize.h"
#endif
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
map<int,vi> qs;
vi test(int i) {
if(qs.count(i)) return qs[i];
else return qs[i] = ask(i);
}
template<typename T> struct fenwick {
int n;
vector<T> fen;
fenwick(){}
fenwick(int nn) {
fen.resize(nn+1);
n = nn;
}
auto sum(int i) {
T ans = 0;
while(i) {
ans+=fen[i];
i&=i-1;
}
return ans;
}
auto query(int l, int r) {
return sum(r+1)-sum(l);
}
void update(int i, T val) {
++i;
while(i<=n) {
fen[i]+=val;
i+= i&(-i);
}
}
};
int worst(int i) {
if(i==0) return 0;
return sqrt(i-1);
}
int find_best(int n) {
int mx=worst(n)+worst(worst(n))+worst(worst(worst(n)))+worst(worst(worst(worst(n))));
int step = max(1,n/mx);
int lolly=0;
for(int i=0;i<n;i+=step) {
auto v = test(i);
lolly = max(lolly,v[0]+v[1]);
}
int left=lolly;
set<int> cand;
fenwick<int> fen(n);
for(int i=0;i<n;++i) cand.insert(i);
while(left--) {
int lo=0,hi=n-1;
while(lo<=hi) {
int mid = (lo+hi)/2;
auto it = cand.lower_bound(mid);
if(it==cand.end()) hi=mid-1;
auto check = *it;
if(check>hi) break;
auto v = test(check);
if(v[0]+v[1]==lolly) {
if(v[0]>fen.query(0,check)) {
hi = mid-1;
} else lo = mid+1;
} else {
if(v[0]+v[1]==0) return check;
cand.erase(check);
fen.update(check,1);
break;
}
}
}
return 0;
}
