Problem: This is a harder version of the problem. In this version q ≤ 200 000.

A sequence of integers is called nice if its elements are arranged in blocks like in [3, 3, 3, 4, 1, 1]. Formally, if two elements are equal, everything in between must also be equal.

Let's define difficulty of a sequence as a minimum possible number of elements to change to get a nice sequence. However, if you change at least one element of value x to value y, you must also change all other elements of value x into y as well. For example, for [3, 3, 1, 3, 2, 1, 2] it isn't allowed to change first 1 to 3 and second 1 to 2. You need to leave 1's untouched or change them to the same value.

You are given a sequence of integers a_1, a_2, …, a_n and q updates.

Each update is of form "i x" — change a_i to x. Updates are not independent (the change stays for the future).

Print the difficulty of the initial sequence and of the sequence after every update.

Input

The first line contains integers n and q (1 ≤ n ≤ 200 000, 0 ≤ q ≤ 200 000), the length of the sequence and the number of the updates.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 200 000), the initial sequence.

Each of the following q lines contains integers i_t and x_t (1 ≤ i_t ≤ n, 1 ≤ x_t ≤ 200 000), the position and the new value for this position.

Output

Print q+1 integers, the answer for the initial sequence and the answer after every update.

Example

Input


5 6
1 2 1 2 1
2 1
4 1
5 3
2 3
4 2
2 1


Output


2
1
0
0
2
3
0

Solution (in CPP):

Solution:
#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;
}