#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "prize.h"
struct Interactive
{
int a[N],n;
void Init(int _n)
{
n=_n;
for(int i=0;i<n;i++) cin>>a[i];
}
vector <int> ask(int u)
{
vector <int> res; res.resize(2);
for(int i=0;i<u;i++) res[0]+=(a[i]<a[u]);
for(int i=u+1;i<n;i++) res[1]+=(a[i]<a[u]);
return res;
}
} IR;
//vector <int> ask(int u) { return IR.ask(u); }
int Before[N],After[N];
void quest(int u)
{
vector <int> vec=ask(u);
Before[u]=vec[0]; After[u]=vec[1];
}
bool Is_Diamond(int u)
{
return Before[u]+After[u]==0;
}
int Find_Diamond(int l,int r)
{
if(r-l<=1) return -1;
if(Before[l]+After[l]==Before[r]+After[r])
{
if(Before[r]==Before[l]) return -1;
int mid=(l+r)>>1;
quest(mid);
if(Is_Diamond(mid)) return mid;
int k=Find_Diamond(l,mid);
if(k>-1) return k;
return Find_Diamond(mid,r);
}
else if(Before[l]+After[l]<Before[r]+After[r])
{
quest(l+1);
if(Is_Diamond(l+1)) return l+1;
return Find_Diamond(l+1,r);
}
else
{
quest(r-1);
if(Is_Diamond(r-1)) return r-1;
return Find_Diamond(l,r-1);
}
}
int find_best(int n)
{
quest(0);
if(Is_Diamond(0)) return 0;
quest(n-1);
if(Is_Diamond(n-1)) return n-1;
return Find_Diamond(0,n-1);
}
/*
int main()
{
freopen("prize.inp","r",stdin);
freopen("prize.out","w",stdout);
int n;
cin>>n;
IR.Init(n);
cout<<find_best(n);
}
*/
