/*
TASK:psort
LANG:C
*/
#include<stdio.h>
#include<math.h>
#define MAXN 50001
#define MAX(a,b) (a)>(b) ? (a) : (b)
int a[MAXN]={0};
int n;
int tree[(1<<16)*2+1]={0};
int p[(1<<17)+1]={0};
int dp[MAXN]={0};
int ans=0;
int c;
int tt;
void add(int ind, int st)
{
    while(ind>0)
    {
        tree[ind]=MAX(st,tree[ind]);
        ind/=2;
    }
}
int query(int ind)
{
    int max=0;
    int fl=0;
    while((ind>0)&&(!p[ind]))
    {
        if(!(ind%2)&&!(p[ind]))
        {
            ind=(ind-1)/2;
            max=MAX(max,tree[ind]);
        }
        else
        {
            if(!(p[ind]))
               {
               ind=ind/2;
               max=MAX(max,tree[ind]);
               }
            if(p[ind])
                max=MAX(max,tree[ind]);
        }
    }
    return max;
}
void init()
{
    int i;
//    freopen("psort.in","r",stdin);
    scanf("%d",&n);
    c=(log(n)/log(2));
    if((int)(pow(2,c))<n)tt=pow(2,c+1);
    else tt=n;
    tt--;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=(1<<17);i*=2)
    {
        p[i]=1;
    }
}
void solve()
{
    int i,j;
    for(i=0;i<n;i++)
    {
        dp[i]=query(a[i]+tt)+1;
        add(tt+a[i],dp[i]);
    }
}
void output()
{
    int i;
    printf("%d\n",n-tree[1]);
}
int main()
{
    init();
    solve();
    output();
    return 0;
}

