#include <bits/stdc++.h>
using namespace std;
const int N = 1000010, inf = 1e9, lim = 1000000;
int a[N], n, q;
int cnt[N << 2], mn[N << 2], tag[N << 2];
void puttag(int k, int x) {
  tag[k] += x;
  mn[k] += x;
}
void pushdown(int k) {
  if (tag[k]) {
    puttag(k << 1, tag[k]);
    puttag(k << 1 | 1, tag[k]);
    tag[k] = 0;
  }
}
void pushup(int k) {
  mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
  cnt[k] = 0;
  if (mn[k] == mn[k << 1]) cnt[k] += cnt[k << 1];
  if (mn[k] == mn[k << 1 | 1]) cnt[k] += cnt[k << 1 | 1];
}
void modify(int l, int r, int L, int R, int x, int k) {
  if (L <= l && r <= R) {
    puttag(k, x);
    return;
  }
  int mid = l + r >> 1;
  pushdown(k);
  if (L <= mid) modify(l, mid, L, R, x, k << 1);
  if (R > mid) modify(mid + 1, r, L, R, x, k << 1 | 1);
  pushup(k);
}
void modify(int l, int r, int p, int x, int k) {
  if (l == r) {
    cnt[k] += x;
    return;
  }
  int mid = l + r >> 1;
  pushdown(k);
  if (p <= mid)
    modify(l, mid, p, x, k << 1);
  else
    modify(mid + 1, r, p, x, k << 1 | 1);
  pushup(k);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  a[0] = inf;
  for (int i = 1; i <= n + 1; i++) {
    if (a[i - 1] > a[i]) modify(0, lim, a[i], min(a[i - 1] - 1, lim), 1, 1);
    if (i <= n) modify(0, lim, a[i], 1, 1);
  }
  int p, x;
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &p, &x);
    if (a[p - 1] > a[p]) modify(0, lim, a[p], min(a[p - 1] - 1, lim), -1, 1);
    if (a[p] > a[p + 1]) modify(0, lim, a[p + 1], a[p] - 1, -1, 1);
    modify(0, lim, a[p], -1, 1);
    a[p] = x;
    if (a[p - 1] > a[p]) modify(0, lim, a[p], min(a[p - 1] - 1, lim), 1, 1);
    if (a[p] > a[p + 1]) modify(0, lim, a[p + 1], a[p] - 1, 1, 1);
    modify(0, lim, a[p], 1, 1);
    printf("%d\n", cnt[1]);
  }
  return 0;
}
