#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[30003],stack[30003];
int find(int R,int k)
{
    int L=0,mid;
    while(R>L)
    {
        mid=(R+L)/2;
        if(stack[mid]>k)
        {
            R=mid;
        }
        else
        {
            L=mid+1;
        }
    }
    return L;
}
int main()
{
	freopen("diningb.in","r",stdin);
	freopen("diningb.out","w",stdout);
    int n,i,j,k;
    scanf("%d",&n);
    for(i=0,k=0;i<n;++i)
    {
        scanf("%d",&a[i]);
        if(!i||stack[k-1]<=a[i])
        {
            stack[k++]=a[i];
        }
        else
        {
            j=find(k,a[i]);
            stack[j]=a[i];
        }
    }
    printf("%d\n",n-k);
    return 0;
}