#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1& a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
struct PII {
  int first, second;
  bool operator==(const PII& other) const {
    return first == other.first && second == other.second;
  }
};
struct SegmentNode {
  int be, en;
  int sum, maxv;
  union {
    struct {
      PII min_to_left, max_to_right;
    };
    struct {
      PII to[2];
    };
  };
  union {
    struct {
      int to_left_max, to_right_max;
    };
    struct {
      int to_max[2];
    };
  };
};
struct SegmentTree {
  int l;
  SegmentNode tree[200100 * 4];
  inline int GetLeft(int no) { return no << 1; }
  inline int GetRight(int no) { return (no << 1) + 1; }
  inline int GetFa(int no) { return no >> 1; }
  inline SegmentTree() { l = 0; }
  void Build(int no, int l, int r) {
    if (l > r) r = l;
    if (l == r) {
      tree[no].be = tree[no].en = l;
      tree[no].min_to_left = tree[no].max_to_right = PII({l, l});
      tree[no].maxv = 1;
      UpdSingle(no);
      return;
    }
    tree[no].be = l;
    tree[no].en = r;
    int mid = (l + r) / 2;
    Build(GetLeft(no), l, mid);
    Build(GetRight(no), mid + 1, r);
    PushUp(no);
  }
  inline void PushUp(int no) {
    SegmentNode* node = tree + no;
    SegmentNode* le = tree + GetLeft(no);
    SegmentNode* ri = tree + GetRight(no);
    node->sum = 0;
    node->maxv = max(le->maxv, ri->maxv);
    node->to_left_max = le->to_left_max;
    node->to_right_max = ri->to_right_max;
    node->min_to_left = le->min_to_left;
    node->max_to_right = ri->max_to_right;
    int flag = 0;
    if (le->max_to_right.first > ri->max_to_right.second) {
      flag |= 1;
      node->to_right_max = max1(node->to_right_max, ri->maxv, le->to_right_max);
      node->max_to_right.first =
          max1(node->max_to_right.first, le->max_to_right.first);
      node->max_to_right.second = le->max_to_right.second;
    } else {
      node->sum += ri->sum;
    }
    if (ri->min_to_left.first < le->min_to_left.second) {
      flag |= 2;
      node->to_left_max = max1(node->to_left_max, le->maxv, ri->to_left_max);
      node->min_to_left.first =
          min1(node->min_to_left.first, ri->min_to_left.first);
      node->min_to_left.second = ri->min_to_left.second;
    } else {
      node->sum += le->sum;
    }
    if (flag == 0 && le->max_to_right.first > ri->min_to_left.first) {
      node->sum += max(0, ri->min_to_left.second - le->max_to_right.second + 1 -
                              max1(le->to_right_max, ri->to_left_max));
    }
  }
  inline void UpdSingle(int no) {
    if (tree[no].max_to_right == tree[no].min_to_left) {
      tree[no].sum = 1 - tree[no].maxv;
    } else {
      tree[no].sum = 0;
    }
    if (tree[no].max_to_right.first != tree[no].en) {
      tree[no].to_right_max = tree[no].maxv;
    } else {
      tree[no].to_right_max = 0;
    }
    if (tree[no].min_to_left.first != tree[no].be) {
      tree[no].to_left_max = tree[no].maxv;
    } else {
      tree[no].to_left_max = 0;
    }
  }
  void UpdMaxv(int loc, int no, int ranmaxv) {
    if (loc <= tree[no].be && loc >= tree[no].en) {
      tree[no].maxv = ranmaxv;
      UpdSingle(no);
      return;
    }
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (loc <= mid)
      UpdMaxv(loc, GetLeft(no), ranmaxv);
    else
      UpdMaxv(loc, GetRight(no), ranmaxv);
    PushUp(no);
  }
  void UpdTo(int loc, int no, int val, int cate) {
    if (loc <= tree[no].be && loc >= tree[no].en) {
      tree[no].to[cate].first = val;
      UpdSingle(no);
      return;
    }
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (loc <= mid)
      UpdTo(loc, GetLeft(no), val, cate);
    else
      UpdTo(loc, GetRight(no), val, cate);
    PushUp(no);
  }
};
SegmentTree sgt;
const int maxn = 200100;
int n, nq;
int arr[maxn];
set<int> occurence[maxn];
void ResetOnePos(int val, int inv) {
  sgt.UpdMaxv(*occurence[val].begin(), 1, inv ? 1 : occurence[val].size());
  sgt.UpdTo(*occurence[val].begin(), 1,
            inv ? *occurence[val].begin() : *occurence[val].rbegin(), 1);
  sgt.UpdMaxv(*occurence[val].rbegin(), 1, inv ? 1 : occurence[val].size());
  sgt.UpdTo(*occurence[val].rbegin(), 1,
            inv ? *occurence[val].rbegin() : *occurence[val].begin(), 0);
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &nq);
  sgt.Build(1, 0, n - 1);
  for (int i = 0; i < n; i++) {
    scanf("%d", arr + i);
    occurence[arr[i]].insert(i);
  }
  for (int i = 0; i < n; i++) {
    if (*occurence[arr[i]].begin() == i) {
      sgt.UpdMaxv(i, 1, occurence[arr[i]].size());
      sgt.UpdTo(i, 1, *occurence[arr[i]].rbegin(), 1);
    }
    if (*occurence[arr[i]].rbegin() == i) {
      sgt.UpdMaxv(i, 1, occurence[arr[i]].size());
      sgt.UpdTo(i, 1, *occurence[arr[i]].begin(), 0);
    }
  }
  printf("%d\n", sgt.tree[1].sum);
  for (int i = 0; i < nq; i++) {
    int loc, val, rval;
    scanf("%d%d", &loc, &val);
    loc--;
    rval = arr[loc];
    ResetOnePos(rval, 1);
    if (occurence[val].size()) ResetOnePos(val, 1);
    occurence[rval].erase(loc);
    arr[loc] = val;
    occurence[val].insert(loc);
    if (occurence[rval].size()) ResetOnePos(rval, 0);
    ResetOnePos(val, 0);
    printf("%d\n", sgt.tree[1].sum);
  }
  return 0;
}
