/*
TASK:psort
LANG:C++
*/

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN (1<<16)

inline int min(int a, int b) {
    return a<b?a:b;
}

inline int max(int a, int b) {
    return a>b?a:b;
}

typedef struct cell {
    int min;
    int max;
    int st;
};

int a[MAXN];
cell dp[MAXN][2];
int N;

inline short det(int pos, int flag, int apos) {
    if (apos > pos) {
        if (dp[pos][flag].max > a[apos]) { 
            return 1;
        }
    }
    else {
        if (dp[pos][flag].min < a[apos]) {
            return 1;
        }
    }
    return 0; 
}

int main() {
    
    int flag = 1;
    
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= N; i++) {
        dp[i][0].min = dp[i][0].max = a[i];
    }
    
    for (int j = 2; j <= N; j++) {
        for (int i = 1; i <= N-j+1; i++) {
            dp[i][flag].st = min ( 
                            dp[i][!flag].st + det(i,!flag, i+j-1),
                            dp[i+1][!flag].st + det(i+1, !flag, i)
                            );
            if (dp[i][flag].st == dp[i][!flag].st + det(i, !flag, i+j-1)) {
                dp[i][flag].min = min(dp[i][!flag].min, a[i+j-1]);
                dp[i][flag].max = max(dp[i][!flag].max, a[i+j-1]);
            }
            else {
                dp[i][flag].min = min(dp[i+1][!flag].min, a[i]);
                dp[i][flag].max = max(dp[i+1][!flag].max, a[i]);                
            }
        }
        flag = !flag;
    }
    
    printf("%d\n", dp[!flag][1].st);

    return 0;
}
