#include <bits/stdc++.h>
using namespace std;
int a[500005], mn[4000005], times[4000005], tag[4000005];
void pushr(int x, int y) {
  tag[x] += y;
  mn[x] += y;
}
void pushdown(int x) {
  if (!tag[x]) return;
  pushr(x * 2, tag[x]);
  pushr(x * 2 + 1, tag[x]);
  tag[x] = 0;
}
void pushup(int x) {
  if (times[x * 2] && mn[x * 2] < mn[x * 2 + 1])
    mn[x] = mn[x * 2], times[x] = times[x * 2];
  else if (mn[x * 2] == mn[x * 2 + 1])
    mn[x] = mn[x * 2], times[x] = times[x * 2] + times[x * 2 + 1];
  else
    mn[x] = mn[x * 2 + 1], times[x] = times[x * 2 + 1];
}
void modify(int l, int r, int x, int a, int b, int c) {
  if (a > r || b < l) return;
  if (l >= a && r <= b) {
    pushr(x, c);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(x);
  if (a <= mid) modify(l, mid, x * 2, a, b, c);
  if (b > mid) modify(mid + 1, r, x * 2 + 1, a, b, c);
  pushup(x);
}
void update(int l, int r, int x, int a, int b) {
  if (l == r) {
    times[x] = b;
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(x);
  if (a <= mid)
    update(l, mid, x * 2, a, b);
  else
    update(mid + 1, r, x * 2 + 1, a, b);
  pushup(x);
}
void modi(int x, int y) {
  if (a[x] > a[x + 1]) modify(1, 1e6, 1, a[x + 1], a[x] - 1, y);
}
int main() {
  int n, q, x, y;
  scanf("%d%d", &n, &q);
  a[0] = 1e6 + 1;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) update(1, 1e6, 1, a[i], 1);
  for (int i = 0; i <= n; i++) modi(i, 1);
  while (q--) {
    scanf("%d%d", &x, &y);
    update(1, 1e6, 1, a[x], 0);
    modi(x - 1, -1), modi(x, -1);
    a[x] = y;
    update(1, 1e6, 1, a[x], 1);
    modi(x - 1, 1), modi(x, 1);
    printf("%d\n", mn[1] == 1 ? times[1] : 0);
  }
  return 0;
}
