#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
ll n,s,k=1,a[100007],l[100007],dp[100007];

void sub1(){
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if (a[i]>a[j]&&dp[i]<dp[j]+a[i]) {
                l[i]=l[j]+1;
                dp[i]=dp[j]+a[i];
            }
        }
        if(dp[i]>s){
            s=dp[i];
            k=l[i];
        }
    }
}
void sub2(){
    vector<pll>dp1;
    for(int i=0;i<n;i++) {
        auto it=lower_bound(dp1.begin(),dp1.end(),make_pair(a[i],0LL));
        if (it!=dp1.begin()){
            it--;
            pll j=*it;
            if(dp[i]<j.first+a[i]){
                l[i]=j.second+1;
                dp[i]=j.first+a[i];
            }
        }
        if(dp[i]>s){
            s=dp[i];
            k=l[i];
        }
        if(dp1.empty()||dp1[dp1.size()-1].first<dp[i])
            dp1.push_back({dp[i],l[i]});
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("CAU4.INP","r",stdin);
    freopen("CAU4.OUT","w",stdout);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        dp[i]=a[i];
        l[i]=1;
    }
    s=dp[0];
    if(n<=2000) sub1();
    else sub2();
    cout<<n-k;
    return 0;
}
