#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int maxt = (1 << 20) + 10;
int mn[maxt], mx[maxt], ansl[maxt], ansr[maxt];
int n, q;
int a[maxn];
int query(int x, int l, int r, int lmn, int rmx) {
  if (l == r || lmn <= rmx || lmn <= mn[x] || mx[x] <= rmx) return 0;
  int mid = (l + r) >> 1;
  int ret = min(lmn, mn[x * 2]) > max(rmx, mx[x * 2 + 1]);
  if (lmn > mx[x * 2] && rmx <= mx[x * 2 + 1])
    ret += ansl[x];
  else
    ret += query(x * 2, l, mid, lmn, max(rmx, mx[x * 2 + 1]));
  if (rmx < mn[x * 2 + 1] && lmn >= mn[x * 2])
    ret += ansr[x];
  else
    ret += query(x * 2 + 1, mid + 1, r, min(lmn, mn[x * 2]), rmx);
  return ret;
}
void build(int x, int l, int r) {
  if (l == r) {
    mn[x] = mx[x] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  mn[x] = min(mn[x * 2], mn[x * 2 + 1]);
  mx[x] = max(mx[x * 2], mx[x * 2 + 1]);
  ansl[x] = query(x * 2, l, mid, 0x3f3f3f3f, mx[x * 2 + 1]);
  ansr[x] = query(x * 2 + 1, mid + 1, r, mn[x * 2], -0x3f3f3f3f);
}
void modify(int x, int l, int r, int p, int v) {
  if (l == r) {
    mn[x] = mx[x] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid)
    modify(x * 2, l, mid, p, v);
  else
    modify(x * 2 + 1, mid + 1, r, p, v);
  mn[x] = min(mn[x * 2], mn[x * 2 + 1]);
  mx[x] = max(mx[x * 2], mx[x * 2 + 1]);
  ansl[x] = query(x * 2, l, mid, 0x3f3f3f3f, mx[x * 2 + 1]);
  ansr[x] = query(x * 2 + 1, mid + 1, r, mn[x * 2], -0x3f3f3f3f);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  build(1, 0, n - 1);
  while (q--) {
    int pos, v;
    scanf("%d%d", &pos, &v);
    pos--;
    modify(1, 0, n - 1, pos, v);
    printf("%d\n", query(1, 0, n - 1, 0x3f3f3f3f, -1) + 1);
  }
  return 0;
}
