#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const long long llinf = (long long)9e18;
const int N = (int)1e6 + 111;
int main() {
  long double x;
  int n, m, ans = 0;
  scanf("%d %d", &n, &m);
  vector<int> a(n);
  for (int i = 0; i < n; i++) scanf("%d %Lf", &a[i], &x);
  vector<int> d(n + 1, inf);
  d[0] = -inf;
  for (int i = 0; i < n; i++) {
    int j = (upper_bound(d.begin(), d.end(), a[i]) - d.begin());
    d[j] = a[i];
    ans = max(ans, j);
  }
  printf("%d", n - ans);
  return 0;
}
