/*
TASK:seq
LANG:C
*/

#include <stdio.h>
#include <stdlib.h>

#define IN "seq.in"
#define OUT "seq.out"
#define MAXN 1000100
#define INF 2000000
#define MIN(a,b) (((a) < (b))?(a):(b))
#define MAX(a,b) (((a) > (b))?(a):(b))
#define MINN(a,b,c,d) MIN(MIN(MIN(a,b),c),d);
#define MAXX(a,b,c,d) MAX(MAX(MAX(a,b),c),d);

#define L 0
#define R 1

int a[MAXN];
int b[MAXN];
int m[2][MAXN] = {};
int l[2];
int N,F=0;
int q,k;

int cmp (const void * a,const void * b) {
    return *((int *) a) -  *((int *) b);
}

int dp[2][2][2];
int w[2][2];

int search (int v) {
    int l = 0,r = N,mid;
    while (r - l > 1) {
          mid = (l+r)/2;
          if (a[mid] < v) {
             l = mid;
          } else {
             r = mid;
          }
    }
    return r;
}
int main () {
//    freopen(IN,"r",stdin);
//    freopen(OUT,"w",stdout);
    int i,t,lmin,lmax,ans,p;

    scanf("%d",&N);

    t = 0;
    
    for (i=1; i<=N; i++) {
        scanf("%d",&t);
        a[i] = b[i] = t;
        m[0][i] = N+1;
        m[1][i] = 0;
    }
    qsort (&a[1],N,sizeof(int),cmp);
    for ( i=1; i<=N; i++) {
        t = search(b[i]);
        if (i < m[0][t]) m[0][t] = i;
        if (i > m[1][t]) m[1][t] = i;
    }



    for (i=1; i<=N; ) {
    t = a[i];
        if (i == 1) {
           dp[F][L][L] = 0;
           dp[F][L][R] = 1;
           dp[F][R][L] = 1;
           dp[F][R][R] = 0;
         } else {
          dp[F][0][0] = dp[F][0][1] = dp[F][1][0] = dp[F][1][1] = INF;
          for (k=0; k<=1; k++) {
              p = l[k];
              for (q=0; q<=1; q++) {
                  if (p > m[q][i]) {
                     dp[F][q][L] = MIN(dp[F][q][L],MIN(dp[!F][k][L],dp[!F][k][R]+1) );
                     dp[F][q][R] = MIN(dp[F][q][R],MIN(dp[!F][k][L]+1,dp[!F][k][R]+2) );
                  } else {
                     dp[F][q][L] = MIN(dp[F][q][L],MIN(dp[!F][k][L]+2,dp[!F][k][R]+1) );
                     dp[F][q][R] = MIN(dp[F][q][R],MIN(dp[!F][k][L]+1,dp[!F][k][R]) );
                  }
              }
          }


        w[0][0] = dp[F][0][0];
        w[0][1] = dp[F][0][1];
        w[1][0] = dp[F][1][0];
        w[1][1] = dp[F][1][1];
        
        if (m[0][i] != m[1][i]) {
           dp[F][L][L] = MINN (w[L][L]+2,w[L][R]+1,w[R][L],w[R][R]+1);
           dp[F][L][R] = dp[F][L][L] + 1;

           dp[F][R][R] = MINN (w[L][L]+1,w[L][R],w[R][L]+1,w[R][R]+2);
           dp[F][R][L] = dp[F][R][R] + 1;
        }
        }
        l[0] = m[0][i];
        l[1] = m[1][i];
        while  ( i <= N && t == a[i]) i++;
        F = !F;
        
    }

    F = !F;
    
    ans = MINN(dp[F][L][L],dp[F][L][R],dp[F][R][L],dp[F][R][R]);
    printf("%d\n",ans);
    
    return 0;
}
