#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,fx[200009],sq=450,lef,rig,mid,MX,LF,lf,O;
int F[200009];
pair <int, int> P[200009];
/*pair <int, int> ask(int q){
int QA=0,WA=0,QQ=0;
for(QQ=0; QQ<q; QQ++){
if(F[QQ]<F[q]) QA++;
}
for(QQ=q+1; QQ<a; QQ++){
if(F[QQ]<F[q]) WA++;
}
return make_pair(QA,WA);
}*/
pair <int, int> Ask(int q){
if(fx[q]==1){
return P[q];
}
fx[q]=1;
vector <int> QA=ask(q);
P[q]=make_pair(QA[0],QA[1]);
return make_pair(QA[0],QA[1]);
}
int find_best(int Nn) {
a=Nn;
MX=0;
for(i=0; i<min(a,sq); i++){
P[i]=Ask(i);
MX=max(MX,P[i].first+P[i].second);
}
LF=0;
while(1){
lef=LF-1;rig=a;e=-1;
while(1){
if(lef+1>=rig){
while(1){e++;e--;}
break;
}
mid=(lef+rig)/2;
while(mid>lef){
P[mid]=Ask(mid);
if(P[mid].first+P[mid].second==MX) break;
mid--;
}
if(mid==lef){
e=lef+1;break;
}
P[mid]=Ask(mid);
if(P[mid].first==lf){
lef=mid;
lf=P[mid].first;
}else{
rig=mid;
}
}
lf++;
P[e]=Ask(e);
if(P[e].first+P[e].second==0){
return e;
}
LF=e+1;
}
return 0;
}
/*int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;
for(i=0; i<a; i++){
cin>>F[i];
}
cout<<find_best(a);
return 0;
}*/
