#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int dp[N],q[N],a[N],len = 0;
bool cmp(int X,int Y){
	return X < Y;
}
int main(){
//	freopen("P3902_1.in","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	a[0] = 0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		int l = 1,r = len;
		while(l < r){
			int mid = (l+r+1)>>1;
			if(a[q[mid]] < a[i]){
				l = mid;
			}else{
				r = mid-1;
			}
		}
		dp[i] = dp[q[l]] + 1;
		if(a[i] < a[q[dp[i]]]){
			q[dp[i]] = i;
		}
//		cout<<dp[i]<<' ';
		len = max(len,dp[i]);
	}
	printf("%d",n-len+1);
}