#include <cstdio>

#define Nmax 5005

using namespace std;
int N,v[Nmax],DP[Nmax],used[Nmax];

void Read()
{
    scanf("%d",&N);

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

}

void Solve()
{
    for(int i = 1; i <= N; ++i)
    {
        DP[i] = 1;
        for(int j = i - 1; j >= 1; --j)
            if(v[i] > v[j] && DP[i] < DP[j] + 1)
            {
                DP[i] = DP[j] + 1;
                used[j] = 1; /// l-am agatat in interiorul unui subsir
            }
    }
    int mini = 999999;
    for(int i = 1; i <= N; ++i)
        if(!used[i])
            if(mini > DP[i])
                mini = DP[i];
    printf("%d\n",mini);

}

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

    Read();
    Solve();

    return 0;
}