#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
template <typename T>
inline T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
inline T min(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline bool repr(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool repl(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline T gcd(T a, T b) {
  T t;
  if (a < b) {
    while (a) {
      t = a;
      a = b % a;
      b = t;
    }
    return b;
  } else {
    while (b) {
      t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
}
template <typename T>
inline T sqr(T x) {
  return x * x;
}
struct Cg {
  __attribute__((always_inline)) inline char operator()() { return getchar(); }
};
struct Cp {
  __attribute__((always_inline)) inline void operator()(char x) { putchar(x); }
};
__attribute__((always_inline)) inline bool IS(char x) {
  return x == 10 || x == 13 || x == ' ';
}
template <typename T>
struct Fr {
  T P;
  __attribute__((always_inline)) inline Fr &operator,(int &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator int() {
    int x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(long long &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator long long() {
    long long x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(char &x) {
    for (x = P(); IS(x); x = P())
      ;
    return *this;
  }
  __attribute__((always_inline)) inline operator char() {
    char x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(char *x) {
    char t = P();
    for (; IS(t); t = P())
      ;
    if (~t) {
      for (; !IS(t) && ~t; t = P()) *x++ = t;
    }
    *x++ = 0;
    return *this;
  }
  __attribute__((always_inline)) inline Fr &operator,(double &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator double() {
    double x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(long double &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator long double() {
    long double x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(unsigned int &x) {
    x = 0;
    unsigned char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  __attribute__((always_inline)) inline operator unsigned int() {
    unsigned int x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(unsigned long long &x) {
    x = 0;
    unsigned char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  __attribute__((always_inline)) inline operator unsigned long long() {
    unsigned long long x;
    *this, x;
    return x;
  }
};
Fr<Cg> in;
template <typename T>
struct Fw {
  T P;
  __attribute__((always_inline)) inline Fw &operator,(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(unsigned int x) {
    if (x) {
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(unsigned int x) {
    if (x) {
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(unsigned long long x) {
    if (x) {
      unsigned char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(unsigned long long x) {
    if (x) {
      unsigned char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(char x) {
    P(x);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(char x) {
    P(x);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(long double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
};
Fw<Cp> out;
const int N = 200007, Br = 112, B = Br + 3, BC = N / Br + 7;
std::set<int> p[N];
int n, m, blo, bc, s[N], su[N], lst[N], cnt[N];
int gmax[BC];
struct cv_t {
  int maxv, tcnt, ans;
} cv[BC][B];
const int B8 = (B + 7) / 8 + 1, BU = B8 * 8;
__attribute__((__aligned__(32))) int maxv[BU], tcnt[BU], ans[BU];
void build(int x) {
  int l = x * blo - blo + 1, r = min(n, x * blo);
  int tmax = l - 1, lsumd = l - 1;
  for (int i = 0, iend = r + 1 - l; i <= iend; i++)
    tcnt[i] = ans[i] = 0, maxv[i] = -1;
  for (int i = l, iend = r; i <= iend; i++) {
    if (!su[i]) continue;
    repr(tmax, lst[su[i]]);
    int C = cnt[su[i]];
    for (int j = 0, jend = r + 2 - l; j < jend; j++) repr(tcnt[j], C);
    if (tmax == i) {
      for (int j = l, jend = lsumd; j <= jend; j++) ans[j - l] += tcnt[j - l];
      for (int j = lsumd + 1, jend = i; j <= jend; j++)
        maxv[j - l] = tcnt[j - l];
      for (int j = l, jend = i; j <= jend; j++) tcnt[j - l] = 0;
      lsumd = i;
    }
  }
  for (int i = 0, iend = r + 1 - l; i <= iend; i++) {
    cv[x][i] = (cv_t){maxv[i], tcnt[i], ans[i]};
  }
  gmax[x] = tmax;
}
inline int get_ans() {
  int t = 0, tcnt = 0, ans = 0;
  for (int i = 1, iend = bc; i <= iend; i++) {
    int l = i * blo - blo + 1, r = min(n, i * blo);
    if (t > r) {
      repr(t, gmax[i]);
      repr(tcnt, cv[i][r + 1 - l].tcnt);
      continue;
    }
    repr(t, l);
    if (cv[i][t - l].maxv == -1) {
      repr(tcnt, cv[i][t - l].tcnt);
      repr(t, gmax[i]);
      continue;
    }
    ans += max(cv[i][t - l].maxv, tcnt);
    ans += cv[i][t - l].ans;
    tcnt = cv[i][t - l].tcnt;
    repr(t, gmax[i]);
  }
  return ans;
}
inline int geb(int x) { return (x - 1) / blo + 1; }
int main() {
  in, n, m;
  blo = Br;
  bc = (n + blo - 1) / blo;
  repr(blo, 1), repl(blo, n);
  for (int i = 1, iend = n; i <= iend; i++) in, s[i];
  for (int i = 1, iend = n; i <= iend; i++) {
    if (!lst[s[i]]) su[i] = s[i];
    lst[s[i]] = i, cnt[s[i]]++;
    p[s[i]].insert(i);
  }
  for (int i = 0, iend = N; i < iend; i++)
    if (lst[i]) su[lst[i]] = i;
  for (int i = 1, iend = bc; i <= iend; i++) build(i);
  out, n - get_ans(), '\n';
  for (int i = 0, iend = m; i < iend; i++) {
    int x, y;
    in, x, y;
    std::set<int> reb;
    if (s[x] != y) {
      int a = s[x], xl = *p[a].begin(), xr = *p[a].rbegin();
      cnt[a]--;
      p[a].erase(x);
      if (!p[a].size()) {
        reb.insert(geb(xl));
        su[xl] = 0;
      } else {
        int nxl = *p[a].begin(), nxr = *p[a].rbegin();
        if (nxl != xl) reb.insert(geb(xl)), su[xl] = 0, su[nxl] = a;
        if (nxr != xr) reb.insert(geb(xr)), su[xr] = 0, su[nxr] = a;
        lst[a] = nxr;
        reb.insert(geb(nxl)), reb.insert(geb(nxr));
      }
      a = s[x] = y;
      cnt[a]++;
      if (!p[a].size()) {
        p[a].insert(x);
        reb.insert(geb(x));
        su[x] = a;
        lst[a] = x;
      } else {
        int nxl = *p[a].begin(), nxr = *p[a].rbegin();
        p[a].insert(x);
        int xl = *p[a].begin(), xr = *p[a].rbegin();
        if (nxl != xl)
          reb.insert(geb(nxl)), su[xl] = a, nxl == nxr ? 0 : su[nxl] = 0;
        if (nxr != xr)
          reb.insert(geb(nxr)), su[xr] = a, nxl == nxr ? 0 : su[nxr] = 0;
        lst[a] = xr;
        reb.insert(geb(xl)), reb.insert(geb(xr));
      }
      for (__typeof((reb).end()) j = (reb).begin(); j != (reb).end(); ++j)
        build(*j);
    }
    out, n - get_ans(), '\n';
  }
}
