//infoarena subsir2
// http://infoarena.ro/problema/subsir2
//O(n^2)
#include <cstdio>
#include <cstdlib>

#define INF 0x7FFFFFFF
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max(a,b) ((a) > (b) ? (a) : (b))

using namespace std;

#define MAX 5000

int v[MAX], N, Lmin, L[MAX];

void calc()
{
    L[N-1] = 1;
    for (int i = N-2; i>=0; i--)
    {
        int vmin = INF, l = INF;
        for (int j = i+1; j<N; j++)
        {

            if (v[j] >= v[i] && v[j] <= vmin && L[j] < l)
                  l = L[j];
            if (v[j] >=v[i] && v[j] <vmin) vmin = v[j];
        };
        if (l==INF) l =0;
        L[i] = l + 1;
    };
};




int main()
{
    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);

    scanf("%d\n", &N);
    for (int i = 0; i<N; i++)
        scanf("%d", &v[i]);

    calc();
    int vmin;
    Lmin = L[0];  vmin = v[0];
    for (int i=1; i<N; i++)
    {
        if (v[i] < vmin ) vmin = v[i];
        else if (v[i] == vmin) vmin++;
        if (v[i] == vmin && L[i] < Lmin)
            Lmin = L[i];
    };



    printf("%d\n", Lmin);
    fclose(stdin);
    fclose(stdout);
    return 0;
};