#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> v;
int a[50000];
void input() {
  double z;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i] >> z;
}
int bs(int s, int f, int x) {
  if (s == f) return s;
  int p = (s + f) / 2;
  if (v[p] > x)
    return bs(s, p, x);
  else
    return bs(p + 1, f, x);
}
int main() {
  ios_base::sync_with_stdio(false);
  input();
  v.push_back(a[1]);
  for (int i = 2; i <= n; i++) {
    if (a[i] >= v[v.size() - 1])
      v.push_back(a[i]);
    else {
      int k = bs(0, v.size() - 1, a[i]);
      v[k] = a[i];
    }
  }
  cout << n - v.size();
}
