// 二分查找时可以直接用upper_bound来找或者自己写个find函数，两个我都试了，时间上几乎没有差别

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define maxn 30008
int data[maxn];
int LIS[maxn], len[maxn], ans;

int find( int x ){
    int l=1, r=len[0], mid;
    while(l <= r) {
       mid = (l+r)>>1;
       if(len[mid] > x) r=mid-1;
       else l= mid+1;
    }
    return l;
};

void get(int *a, int n){
    LIS[0]=1, len[1] = a[0];
    len[0] = 1;
    for( int i=1; i<n; ++i ){
        if(a[i] >= len[len[0] ] ) {
             LIS[i] = ++len[0];
             len[len[0] ] = a[i];
        }else {
            //int x = upper_bound(len+1, len+1+len[0], a[i])-len;
            int x = find(a[i]);
            LIS[i] = x;
           // cout<<"***" << x << endl;
            len[LIS[i] ] = a[i];
        }
        if(LIS[i] > ans) ans = LIS[i];
    }
};

int main( int argc, char** argv  ) {
    int n;
    while( ~scanf("%d", &n) ) {
        for(int i=0; i<n; ++i )
          scanf("%d", data+i);
        ans = 1;
        get(data, n);
        reverse(data, data+n);
        get(data, n);
        printf("%d\n", n-ans);
    }
    return (EXIT_SUCCESS);
};