#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

long long N, X[1 << 18];
long long B[1 << 18], cnt;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> X[i];
	for (int i = 0; i < N; i++) X[i] = (1000000LL * X[i]) + 1LL * i;
	for (int i = 0; i < N; i++) {
		int pos1 = lower_bound(B, B + cnt, X[i] + 1) - B;
		if (pos1 == cnt) cnt++;
		B[pos1] = X[i];
	}
	cout << N - cnt << endl;
	return 0;
}