#include <bits/stdc++.h> using namespace std; const int M = 1e5 + 5, INF = 1e9; int a[M], f1[M], f2[M], g[M], len, ans = -INF; int main() { int n; scanf ("%d", &n); for (int i = 1; i <= n; i++) scanf ("%d", &a[i]); len = 0; for (int i = 1; i <= n; i++) { int pos = lower_bound(g + 1, g + len + 1, a[i]) - g; f1[i] = pos; g[pos] = a[i]; len = max(len, pos); } len = 0; memset(g, 0, sizeof g); for (int i = n; i >= 1; i--) { int pos = lower_bound(g + 1, g + len + 1, a[i]) - g; f2[i] = pos; g[pos] = a[i]; len = max(len, pos); } for (int i = 1; i <= n; i++) ans = max(ans, f1[i] + f2[i] - 1); cout << n - ans; return 0; }