#include<bits/stdc++.h>
#ifndef SKY
#include "prize.h"
#endif // SKY
using namespace std;
#define N 200010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
int cuctrai,cucphai,n,lolipop;
int ktr[N];
ii f[N];
#ifdef SKY
int p[N];
vector<int> ask(int i)
{
cout<<"ask "<<i<<endl;
vector<int>res(2,0);
for(int j=0;j<i;j++)
if(p[j]<p[i])
res[0]++;
for(int j=i+1;j<n;j++)
if(p[j]<p[i])
res[1]++;
// cout<<i<<endl;
// for(int j=0;j<n;j++)cout<<p[j]<<" ";cout<<endl;
// cout<<res[0]<<" "<<res[1]<<endl;
return res;
}
#endif // SKY
int query=0;
vector<int>myAsk(int i)
{
query++;
assert(query<=1e4);
if(ktr[i]!=-1)
return {f[i].fs,f[i].sc};
vector<int>res=ask(i);
ktr[i]=1;
f[i]={res[0],res[1]};
return res;
}
vector<ii>lis;
void solve(int l,int r,int left_child,int right_child)
{
l=max(l,cuctrai);
r=min(r,cucphai);
if(l>r)
return;
int mid=(l+r)/2,v=mid,u=mid-1;
while(1)
{
l=max(l,cuctrai);
r=min(r,cucphai);
if(l>r)
return;
vector<int>s;
if(u>=l)
{
s=myAsk(u);
if(s[0]+s[1]!=lolipop)
{
lis.pb({u,s[0]+s[1]});
if(s[0]==0)
{
cuctrai=v+1;
u=l-1;
}
if(s[1]==0)
{
cucphai=v-1;
v=r+1;
}
u--;
}else
{
if(s[0]-left_child!=0)
{
solve(l,u-1,left_child,s[1]);
}
if(s[1]-right_child!=0)
{
solve(v,r,s[0],right_child);
}
return;
}
}
if(v<=r)
{
s=myAsk(v);
if(s[0]+s[1]!=lolipop)
{
lis.pb({v,s[0]+s[1]});
if(s[0]==0)
{
cuctrai=v+1;
u=l-1;
}
if(s[1]==0)
{
cucphai=v-1;
v=r+1;
}
v++;
}else
{
if(s[0]-left_child!=0)
{
solve(l,u,left_child,s[1]);
}
if(s[1]-right_child!=0)
{
solve(v+1,r,s[0],right_child);
}
return;
}
}
if(u<l&&v>r)
return;
}
/* for(int i=mid;i<=r;i++)
{
vector<int>s=myAsk(i);
if(s[0]+s[1]!=lolipop)
{
lis.pb(i);
}else
{
if(s[0]-left_child!=0)
{
solve(l,mid-1,left_child,s[1]);
}
if(s[1]-right_child!=0)
{
solve(i+1,r,s[0],right_child);
}
return;
}
}
for(int i=mid-1;i>=l;i--)
{
vector<int>s=myAsk(i);
if(s[0]+s[1]!=lolipop)
{
lis.pb(i);
}else
{
if(s[0]-left_child!=0)
{
solve(l,i-1,left_child,s[1]);
}
}
}*/
}
int find_best(int cc)
{
memset(ktr,-1,sizeof(ktr));
n=cc;
cuctrai=0;
cucphai=n-1;
lis.clear();
if(n<=500)
{
for(int i=0;i<n;i++)
{
vector<int>s=myAsk(i);
if(s[0]==0&&s[1]==0)
return i;
}
}
lolipop=0;
for(int i=0;i<sqrt(n)+100;i++)
{
vector<int>s=myAsk(i);
lolipop=max(lolipop,s[0]+s[1]);
}
solve(0,n-1,0,0);
for(auto i:lis)
{
if(i.sc==0)
return i.fs;
}
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>p[i];
cout<<find_best(n);
cout<<endl<<query<<endl;
return 0;
}
#endif // SKY
