#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
  return os << "(" << x.first << "," << x.second << ")";
}
struct SegTree {
  struct Node {
    int mn = 0;
    int numMn = 1;
    int mx = 0;
    int mxl = 0;
    int mxr = 0;
    long long sumMx = 0;
    int prop = 0;
    void apply(int s, int e, int v, int w = -1) {
      mn += v;
      prop += v;
      if (w != -1) mx = w;
    }
  };
  inline Node combine(const Node& a, const Node& b) {
    Node res;
    res.mn = min(a.mn, b.mn);
    res.numMn = 0;
    res.mx = max(a.mx, b.mx);
    if (a.mn == res.mn && b.mn == res.mn) {
      res.sumMx = a.sumMx + b.sumMx - a.mxr - b.mxl + max(a.mxr, b.mxl);
      res.numMn = a.numMn + b.numMn;
      res.mxl = a.mxl;
      res.mxr = b.mxr;
    } else if (a.mn == res.mn) {
      res.sumMx = a.sumMx - a.mxr + max(a.mxr, b.mx);
      res.numMn = a.numMn;
      res.mxl = a.mxl;
      res.mxr = max(a.mxr, b.mx);
    } else {
      res.sumMx = b.sumMx - b.mxl + max(a.mx, b.mxl);
      res.numMn = b.numMn;
      res.mxl = max(a.mx, b.mxl);
      res.mxr = b.mxr;
    }
    return res;
  }
  inline void push(int sn, int s, int e) {
    if (tree[sn].prop) {
      int m = (s + e) >> 1, lsn = sn * 2, rsn = sn * 2 + 1;
      tree[lsn].apply(s, m, tree[sn].prop);
      tree[rsn].apply(m + 1, e, tree[sn].prop);
      tree[sn].prop = 0;
    }
  }
  int start, end;
  vector<Node> tree;
  void build(int sn, int s, int e) {
    if (s == e) {
      return;
    }
    int m = (s + e) >> 1, lsn = sn * 2, rsn = sn * 2 + 1;
    build(lsn, s, m);
    build(rsn, m + 1, e);
    tree[sn] = combine(tree[lsn], tree[rsn]);
  }
  template <typename T>
  void build(int sn, int s, int e, vector<T>& v) {
    if (s == e) {
      return;
    }
    int m = (s + e) >> 1, lsn = sn * 2, rsn = sn * 2 + 1;
    build(lsn, s, m, v);
    build(rsn, m + 1, e, v);
    tree[sn] = combine(tree[lsn], tree[rsn]);
  }
  template <typename... T>
  void update(int sn, int s, int e, int qs, int qe, const T&... v) {
    if (qs <= s && e <= qe) {
      tree[sn].apply(s, e, v...);
      return;
    }
    int m = (s + e) >> 1, lsn = sn * 2, rsn = sn * 2 + 1;
    push(sn, s, e);
    if (qs <= m) update(lsn, s, m, qs, qe, v...);
    if (qe > m) update(rsn, m + 1, e, qs, qe, v...);
    tree[sn] = combine(tree[lsn], tree[rsn]);
  }
  Node query(int sn, int s, int e, int qs, int qe) {
    if (qs <= s && e <= qe) return tree[sn];
    int m = (s + e) >> 1, lsn = sn * 2, rsn = sn * 2 + 1;
    push(sn, s, e);
    if (qe <= m) return query(lsn, s, m, qs, qe);
    if (qs > m) return query(rsn, m + 1, e, qs, qe);
    return combine(query(lsn, s, m, qs, qe), query(rsn, m + 1, e, qs, qe));
  }
  void query(int sn, int s, int e, int qs, int qe,
             const function<void(Node&, int, int)>& f) {
    if (qs <= s && e <= qe) return f(tree[sn], s, e);
    int m = (s + e) >> 1, lsn = sn * 2, rsn = sn * 2 + 1;
    push(sn, s, e);
    if (qs <= m) query(lsn, s, m, qs, qe, f);
    if (qe > m) query(rsn, m + 1, e, qs, qe, f);
  }
  SegTree(int n) : SegTree(0, n - 1) {}
  SegTree(int _start, int _end) : start(_start), end(_end) {
    int n = end - start + 1;
    int maxs = n == 1 ? 2 : 1 << (33 - __builtin_clz(n - 1));
    tree.resize(maxs);
    build(1, start, end);
  }
  template <typename T>
  SegTree(vector<T>& v) {
    int n = v.size();
    int maxs = n == 1 ? 2 : 1 << (33 - __builtin_clz(n - 1));
    tree.resize(maxs);
    start = 0;
    end = n - 1;
    build(1, start, end, v);
  }
  Node query(int qs, int qe) { return query(1, start, end, qs, qe); }
  Node query(int p) { return query(1, start, end, p, p); }
  void query(int qs, int qe, const function<void(Node&, int, int)>& f) {
    if (qs > qe) return;
    query(1, start, end, qs, qe, f);
  }
  template <typename... T>
  void update(int qs, int qe, const T&... v) {
    update(1, start, end, qs, qe, v...);
  }
};
using Node = SegTree::Node;
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  const int MX = 200000;
  vector<int> a(n);
  vector<set<int>> occ(MX + 1);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    occ[a[i]].insert(i);
  }
  SegTree st(n);
  for (int i = 1; i <= MX; ++i) {
    if (occ[i].empty()) continue;
    int a = *occ[i].begin();
    int b = *occ[i].rbegin();
    if (a == b) continue;
    st.update(a, b - 1, 1);
    st.update(a, a, 0, occ[i].size() - 1);
  }
  auto ans = st.query(0, n - 1);
  assert(ans.mn == 0);
  printf("%lld\n", n - (ans.sumMx + ans.numMn));
  while (q--) {
    int i, x;
    scanf("%d%d", &i, &x);
    --i;
    if (a[i] != x) {
      int c = *occ[a[i]].begin();
      int d = *occ[a[i]].rbegin();
      if (c != d) {
        st.update(c, d - 1, -1);
        st.update(c, c, 0, 0);
      }
      occ[a[i]].erase(i);
      if (!occ[a[i]].empty()) {
        c = *occ[a[i]].begin();
        d = *occ[a[i]].rbegin();
        if (c != d) {
          st.update(c, d - 1, 1);
          st.update(c, c, 0, occ[a[i]].size() - 1);
        }
      }
      if (!occ[x].empty()) {
        c = *occ[x].begin();
        d = *occ[x].rbegin();
        if (c != d) {
          st.update(c, d - 1, -1);
          st.update(c, c, 0, 0);
        }
      }
      occ[x].insert(i);
      c = *occ[x].begin();
      d = *occ[x].rbegin();
      if (c != d) {
        st.update(c, d - 1, 1);
        st.update(c, c, 0, occ[x].size() - 1);
      }
      a[i] = x;
    }
    auto ans = st.query(0, n - 1);
    assert(ans.mn == 0);
    printf("%lld\n", n - (ans.sumMx + ans.numMn));
  }
}
