#include<bits/stdc++.h>
using namespace std;
#include "prize.h"
constexpr int maxn = 2e5;
const vector<int> good = {0, 0};
struct BIT
{
int bit[maxn];
void build() {
for(int i = 1; i < maxn; i++)
bit[i] = i&-i;
}
void upd(int x, int v) {
for(x++; x < maxn; x += x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 0;
for(x++; x > 0; x -= x&-x)
ans += bit[x];
return ans;
}
int bs(int x) {
int pos = 0;
for(int l = 20; l >= 0; l--) {
if(pos + (1 << l) >= maxn) continue;
if(bit[pos + (1 << l)] < x)
pos += (1 << l), x -= bit[pos];
}
return pos;
}
int itv(int l, int r) {
return query(r)-query(l);
}
} bit1, bit2;
vector<int> val[maxn];
int find_best(int n) {
bit1.build();
int base = 0;
for(int i = 0; i < min(n, 475); i++) {
vector<int> a = ask(i);
base = max(base, a[0]+a[1]);
}
set<int> st;
int qtd = 0;
while(1) {
int l = 1, r = n-qtd;
while(l <= r) {
int m = (l+r) >> 1;
int pos = bit1.bs(m);
++qtd;
bit1.upd(pos, -1);
vector<int> a = ask(pos);
val[pos] = a;
if(a == good) return pos;
if(a[0]+a[1] == base) {
if(a[0]-bit2.query(pos)>a[1]-bit2.itv(pos, maxn-1)) r = m-1;
else l = m+1;
auto it = st.upper_bound(pos);
if(it != st.end()) {
if((val[(*it)][0] - val[pos][0] - bit2.itv(*it, pos)) == 0) {
for(int i = pos+1; i < (*it); ++i)
bit1.upd(i, -1), ++qtd;
}
}
if(it != st.begin()) {
--it;
if((val[pos][0] - val[(*it)][0] - bit2.itv(pos, *it)) == 0) {
for(int i = (*it)+1; i < pos; ++i)
bit1.upd(i, -1), ++qtd;
}
}
st.insert(pos);
} else {
bit2.upd(pos, 1);
break;
}
r = min(r, n-qtd);
}
}
}
