#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int m = 1 << 19;
  vector<int> tree_lazy((size_t)m * 2 + 1, 0);
  vector<int> tree_min((size_t)m * 2 + 1, 0);
  vector<int> tree_count((size_t)m * 2 + 1, 0);
  vector<int> tree_max((size_t)m * 2 + 1, 0);
  vector<int> tree_sum((size_t)m * 2 + 1, 0);
  vector<int> tree_left((size_t)m * 2 + 1, 0);
  vector<int> tree_right((size_t)m * 2 + 1, 0);
  function<void(int, int, int)> tree_build = [&](int tree_v, int tree_l,
                                                 int tree_r) {
    tree_count[tree_v] = tree_r - tree_l + 1;
    if (tree_l != tree_r) {
      tree_build(tree_v * 2 + 0, tree_l, tree_l + (tree_r - tree_l) / 2);
      tree_build(tree_v * 2 + 1, tree_r - (tree_r - tree_l) / 2, tree_r);
    }
  };
  tree_build(1, 0, m - 1);
  vector<int> c((size_t)m, 0), d((size_t)m, 0);
  function<void(int, int, int, int, int, int, int, int)> tree_update =
      [&](int tree_v, int tree_l, int tree_r, int l, int r, int x, int y,
          int z) {
        if (tree_l != tree_r) {
          tree_min[tree_v * 2 + 0] += tree_lazy[tree_v];
          tree_min[tree_v * 2 + 1] += tree_lazy[tree_v];
          tree_lazy[tree_v * 2 + 0] += tree_lazy[tree_v];
          tree_lazy[tree_v * 2 + 1] += tree_lazy[tree_v];
          tree_lazy[tree_v] = 0;
        }
        if (tree_l >= l && tree_r <= r) {
          tree_min[tree_v] += x;
          tree_lazy[tree_v] += x;
          if (y != -1) {
            tree_right[tree_v] = tree_left[tree_v] = tree_sum[tree_v] =
                tree_max[tree_v] = y;
          }
        } else if (tree_l <= r && tree_r >= l) {
          tree_update(tree_v * 2 + 0, tree_l, tree_l + (tree_r - tree_l) / 2, l,
                      r, x, y, z);
          tree_update(tree_v * 2 + 1, tree_r - (tree_r - tree_l) / 2, tree_r, l,
                      r, x, y, z);
          tree_min[tree_v] =
              min(tree_min[tree_v * 2 + 0], tree_min[tree_v * 2 + 1]);
          tree_max[tree_v] =
              max(tree_max[tree_v * 2 + 0], tree_max[tree_v * 2 + 1]);
          if (tree_min[tree_v * 2 + 0] < tree_min[tree_v * 2 + 1]) {
            tree_count[tree_v] = tree_count[tree_v * 2 + 0];
            tree_sum[tree_v] =
                (tree_sum[tree_v * 2 + 0] - tree_right[tree_v * 2 + 0]) +
                max(tree_right[tree_v * 2 + 0], tree_max[tree_v * 2 + 1]);
            tree_left[tree_v] = tree_left[tree_v * 2 + 0];
            tree_right[tree_v] =
                max(tree_right[tree_v * 2 + 0], tree_max[tree_v * 2 + 1]);
          } else if (tree_min[tree_v * 2 + 1] < tree_min[tree_v * 2 + 0]) {
            tree_count[tree_v] = tree_count[tree_v * 2 + 1];
            tree_sum[tree_v] =
                max(tree_max[tree_v * 2 + 0], tree_left[tree_v * 2 + 1]) +
                (tree_sum[tree_v * 2 + 1] - tree_left[tree_v * 2 + 1]);
            tree_left[tree_v] =
                max(tree_max[tree_v * 2 + 0], tree_left[tree_v * 2 + 1]);
            tree_right[tree_v] = tree_right[tree_v * 2 + 1];
          } else {
            tree_count[tree_v] =
                tree_count[tree_v * 2 + 0] + tree_count[tree_v * 2 + 1];
            tree_sum[tree_v] =
                (tree_sum[tree_v * 2 + 0] - tree_right[tree_v * 2 + 0]) +
                max(tree_right[tree_v * 2 + 0], tree_left[tree_v * 2 + 1]) +
                (tree_sum[tree_v * 2 + 1] - tree_left[tree_v * 2 + 1]);
            tree_left[tree_v] = tree_left[tree_v * 2 + 0];
            tree_right[tree_v] = tree_right[tree_v * 2 + 1];
          }
        }
      };
  int n, q;
  cin >> n >> q;
  vector<int> a((size_t)n);
  vector<set<int>> b((size_t)200000 + 1);
  for (int i = 0; i < n; i++) {
    b[0].insert(i);
  }
  tree_update(1, 0, m - 1, 0, (n - 1) * 2, 1, -1, 0);
  tree_update(1, 0, m - 1, n * 2, m - 1, 1 << 18, -1, 0);
  tree_update(1, 0, m - 1, 0, 0, 0, n, 0);
  auto update = [&](int x, int y) {
    int z = a[x];
    for (int w : {y, z}) {
      if (!b[w].empty()) {
        tree_update(1, 0, m - 1, *b[w].begin() * 2, *b[w].rbegin() * 2, -1, -1,
                    0);
        tree_update(1, 0, m - 1, *b[w].begin() * 2, *b[w].begin() * 2, 0, 0, 0);
      }
    }
    b[z].erase(x);
    a[x] = y;
    b[y].insert(x);
    for (int w : {y, z}) {
      if (!b[w].empty()) {
        tree_update(1, 0, m - 1, *b[w].begin() * 2, *b[w].rbegin() * 2, 1, -1,
                    0);
        tree_update(1, 0, m - 1, *b[w].begin() * 2, *b[w].begin() * 2, 0,
                    b[w].size(), 0);
      }
    }
  };
  for (int i = 0; i < n; i++) {
    int j;
    cin >> j;
    update(i, j);
  }
  cout << n - tree_sum[1] << "\n";
  for (int t = 0; t < q; t++) {
    int x, y;
    cin >> x >> y;
    x--;
    update(x, y);
    cout << n - tree_sum[1] << "\n";
  }
  return 0;
}
