#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
int maxn, abi[200001];
vector<int> v[200001];
void update_abi(int xf, int yf){
while(xf<=maxn){
abi[xf]+=yf;
xf+=xf&(-xf);
}
return;
}
int query_abi1(int xf){
int cr=0;
while(xf>0){
cr+=abi[xf];
xf-=xf&(-xf);
}
return cr;
}
int query_abi2(int xf){
int cr=0, cf=0;
for(int i=18; i>=0; i--){
if(cr+(1<<i)<=maxn){
if(cf+(1<<i)-abi[cr+(1<<i)]<xf){
cf+=(1<<i)-abi[cr+(1<<i)];
cr+=(1<<i);
}
}
}
return cr;
}
int find_best(int n) {
if(n<=5000){
for(int i = 0; i < n; i++) {
vector<int> res = ask(i);
if(res[0] + res[1] == 0)
return i;
}
}
else{
maxn=n;
for(int i = 0; i < 500; i++) {
v[i]=ask(i);
if(v[i][0]+v[i][1]==0)return i;
}
int x=0, y=0;
for(int i = 0; i < 500; i++){
x=max(x, v[i][0]+v[i][1]);
}
y=x;
for(int i = 0; i < 500; i++){
if(v[i][0]+v[i][1]!=x){
y--;
update_abi(i+1, 1);
}
}
int l, r, z, c[20];
for(int i=1; i*500<n; i++){
l=i*500;
r=min(l+500-1, n-1);
z=l-query_abi1(l+1)+1;
while(l<=r){
v[r]=ask(r);
if(v[r][0]+v[r][1]!=x){
update_abi(r+1, 1);
if(v[r][0]+v[r][1]==0)return r;
r--;
y--;
}
else break;
}
if(l>r||v[r][0]==query_abi1(r+1))continue;
c[0]=v[r][0]-query_abi1(r);
for(int t=0; t<c[0]; t++){
r--;
c[1]=l;
c[3]=r;
while(c[1]<=c[3]){
c[2]=(c[1]+c[3])/2;
c[4]=query_abi2(c[2]-l+z);
v[c[4]]=ask(c[4]);
if(v[c[4]][0]+v[c[4]][1]!=x){
y--;
update_abi(c[4]+1, 1);
if(v[c[4]][0]+v[c[4]][1]==0)return c[4];
break;
}
if(v[c[4]][0]==query_abi1(c[4]+1))c[1]=c[2]+1;
else c[3]=c[2]-1;
}
}
}
}
return 0;
}
