#include <bits/stdc++.h>

#define NMax 5005
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("secv.in");
ofstream g("secv.out");
struct asd{
    int nr,ind;
}dp[NMax];

int n,cont,ind,ANS;
int a[NMax],b[NMax];

int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i){
        f >> a[i];
        b[i] = a[i];
    }

    sort(b + 1, b + 1 + n);
    cont = 1;
    for(int i = 1; i <= n; ++i){
        if(b[i] != b[i - 1]){
            for(int j = 1; j <= n; ++j){
                if(a[j] == b[i]){
                    a[j] = cont;
                }
            }
            ++cont;
        }
    }


    for(int i = n; i >= 1; --i){
        dp[i].nr = 1;
        ind = i;
        dp[i].ind = i;
        int mx = 0;
        for(int j = i + 1; j <= n; ++j){
            if(dp[i].nr < dp[i].nr + dp[j].nr && a[j] > a[i]){
                if(mx < dp[j].nr){
                    mx = dp[j].nr;
                    ind = dp[j].ind;
                }
            }
        }
        dp[i].nr += mx;
        dp[i].ind = ind;
    }
    cont--;
    int ANS = INF;
    for(int i = 1; i <= n; ++i)
        if(dp[i].nr == cont){
            ANS = min(ANS,dp[i].ind - i + 1);
        }
    g << ANS << '\n';
    return 0;
}