#include <bits/stdc++.h>
const int N = 500007;
char ibuf[1 << 24], *iS = ibuf;
int a[N], cnt[2 * N], t[8 * N], tag[8 * N];
int read() {
  int x = 0;
  while (isspace(*iS)) ++iS;
  while (isdigit(*iS)) (x *= 10) += *iS++ & 15;
  return x;
}
void pushup(int p, int l, int r) {
  t[p] = (l == r ? !!cnt[l] : t[p << 1] + t[p << 1 | 1]) * !tag[p];
}
void update(int p, int l, int r, int L, int R, int x) {
  if (L > r || l > R || L > R) return;
  if (L <= l && r <= R) return tag[p] += x, pushup(p, l, r), void();
  update(p << 1, l, ((l + r) / 2), L, R, x),
      update(p << 1 | 1, ((l + r) / 2) + 1, r, L, R, x), pushup(p, l, r);
}
void change() {
  int p = read(), x = read();
  update(1, 1, 1000000, a[p - 1] + 1, a[p], -1),
      update(1, 1, 1000000, a[p] + 1, a[p + 1], -1), --cnt[a[p]],
      update(1, 1, 1000000, a[p], a[p], 0);
  ++cnt[a[p] = x], update(1, 1, 1000000, a[p], a[p], 0),
      update(1, 1, 1000000, a[p - 1] + 1, a[p], 1),
      update(1, 1, 1000000, a[p] + 1, a[p + 1], 1);
  printf("%d\n", t[1]);
}
int main() {
  fread(ibuf, 1, 1 << 24, stdin);
  int n = read(), m = read();
  a[0] = 1e9;
  for (int i = 1; i <= n; ++i)
    ++cnt[a[i] = read()], update(1, 1, 1000000, a[i], a[i], 0),
        update(1, 1, 1000000, a[i - 1] + 1, a[i], 1);
  while (m--) change();
}
