特殊的排列

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

ll read() {
	ll ret = 0, flag = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		ret = (ret << 3) + (ret << 1) + (ch ^ '0');
		ch = getchar();
	}
	return ret * flag;
}

ll n, a[100005], b[100005];
ll maxn, maxst;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		b[a[i]] = i;
	}
	ll st = 1; 
	for (int i = 2; i <= n; i++) {
		if (b[i] < b[i-1]) {
			if (i - st > maxn) {
				maxn = i - st;
			}
			st = i;
		} 
	}
	if (n - st + 1 > maxn) maxn = n - st + 1; 
	printf("%lld\n", n - maxn);
	return 0;	
}