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

#define NMAX 5005
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))

int N, a[NMAX], b[NMAX], c[NMAX], i, j, p[NMAX][NMAX], nb, sol = -1;

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

void print()
{
    for (i = 1; i <= nb; i++)
        printf("%d ", b[i]);
    printf("\n");

    for (i = 1; i <= nb; i++)
    {
        for (j = 1; j <= N; j++)
        {
            if (a[j] == b[i])
                printf("*%d ", p[i][j]&0xffff);
            else
                printf("%2d ", p[i][j]&0xffff);
        }
        printf("\n");
    }
    printf("\n");
}

int main()
{
    FILE *in, *out;
    in  = fopen("secv.in", "r");
    out = fopen("secv.out", "w");

    fscanf(in, "%d\n", &N);
    for (i = 1; i <= N; i++)
    {
        fscanf(in, "%d", a+i);
        c[i] = a[i];
    }
    qsort(&c[1], N, sizeof(int), cmp);

    nb = 1;
    b[nb] = c[1];
    for (i = 2; i <= N; i++)
    {
        if (c[i] > b[nb])
            b[++nb] = c[i];
    }

    for (i = 1; i <= nb; i++)
    {
    for (j = 1; j <= N; j++)
    {
        if (a[j] == b[i])
        {
            p[i][j] = 1 + (p[i-1][j-1]&0xffff);
            if (i == 1 || j == 1)
                p[i][j] += (j<<16);
            else
                p[i][j] += (p[i-1][j-1]&0xffff0000);
        }
        else
        {
            p[i][j] = MAX(p[i-1][j], p[i][j-1]);
            if ((p[i-1][j]&0xffff) > (p[i][j-1]&0xffff))
                p[i][j] = p[i-1][j];
            else if ((p[i][j-1]&0xffff) > (p[i-1][j]&0xffff))
                p[i][j] = p[i][j-1];
            else
                p[i][j] = ((MAX(p[i][j-1]>>16, p[i-1][j]>>16)) << 16) + (p[i][j-1]&0xffff);
        }
        //printf("%2d ", p[i][j]>>16);
    }
    //printf("\n");
    }

    j = N;
    while((p[nb][j]&0xffff) == nb)
    {
        //printf("j = %d   st = %d   sol = %d\n", j, p[nb][j]>>16, sol);
        if (sol == -1 || j - (p[nb][j]>>16) + 1 < sol)
            sol = j - (p[nb][j]>>16) + 1;
        j--;
    }
   
    //printf("\n");
    //print();

    fprintf(out, "%d\n", sol);

    fclose(in);
    fclose(out);
    return 0;
}