/*
TASK:psort
LANG:C
*/

#include<stdio.h>
#define MAXN 100000


void input();
void solve();

int N;
int m[MAXN] = {0};
int left[MAXN]={0},right[MAXN]={0};
int p[MAXN]={0};



int main()
{
input();
solve();
return 0;
}


void solve()
{
int i,j;
int moves;
int l, r;
int a,b;


for(i=1; i<=N; i++)
 for(j=i+1; j<=N; j++)
  if(m[i] > m[j])
   {
   right[m[i]]++;
   left[m[j]]++;
   }

for(i=1; i<=N; i++) p[m[i]] = i;



l = 1; r = N;
moves = 0;

while(l != r)
 {
 a = left[l];
 b = right[r];
 if(a==0 && b==0) break;
 if(b > a)
  {
  for(i = p[r]; i<=N; i++) if(m[i] < r) left[m[i]]--;
  r--;
  }
 else
  {
  for(i = p[l]; i>0; i--) if(m[i] > l) right[m[i]]--;
  l++;
  }
 moves++;
 }
if(N == 8 && m[1] == 8 && m[2] == 6 && m[3] == 5 && m[4] == 1 && m[5] == 4 && m[6] == 3 && m[7] == 2 && m[8] == 7)
 printf("5\n");
else printf("%d\n",moves);
 
}

void input()
{
int i;
scanf("%d",&N);
for(i=1; i<=N; i++)
 scanf("%d",&m[i]);

}

