#include <bits/stdc++.h>
using namespace std;
int n, a[500000];
int tree[1 << 20], pre[1 << 20], occ[1 << 20];
int build() {
  int i;
  for (i = 0; i < n; i++) occ[i + n] = 1;
  for (i = n - 1; i > 0; i--) occ[i] = occ[i << 1] + occ[(i << 1) | 1];
  return 0;
}
int update(int as, int ae, int num) {
  int i = as + n;
  tree[i] += num, pre[i] = tree[i], i >>= 1;
  while (i > 0) {
    tree[i] = tree[i << 1] + tree[(i << 1) | 1];
    pre[i] = min(pre[i << 1], tree[i << 1] + pre[(i << 1) | 1]), occ[i] = 0;
    if (pre[i << 1] == pre[i]) occ[i] += occ[i << 1];
    if (tree[i << 1] + pre[(i << 1) | 1] == pre[i]) occ[i] += occ[(i << 1) | 1];
    i >>= 1;
  }
  i = ae + n, tree[i] -= num, pre[i] = tree[i], i >>= 1;
  while (i > 0) {
    tree[i] = tree[i << 1] + tree[(i << 1) | 1];
    pre[i] = min(pre[i << 1], tree[i << 1] + pre[(i << 1) | 1]), occ[i] = 0;
    if (pre[i << 1] == pre[i]) occ[i] += occ[i << 1];
    if (tree[i << 1] + pre[(i << 1) | 1] == pre[i]) occ[i] += occ[(i << 1) | 1];
    i >>= 1;
  }
  return 0;
}
pair<int, int> tree2[1 << 20], inter[1 << 20];
int pos[1 << 20];
pair<int, int> com(pair<int, int> a, pair<int, int> b) {
  return make_pair(min(a.first, b.first), max(a.second, b.second));
}
int getInter(int s, int e, int i) {
  if (tree2[2 * i + 1].first > tree2[2 * i + 2].second)
    inter[i] = make_pair(-1, -1);
  else {
    int j = 2 * i + 2;
    while (pos[j] == -1) {
      if (tree2[2 * i + 1].first < tree2[2 * j + 2].second)
        j = 2 * j + 2;
      else
        j = 2 * j + 1;
    }
    inter[i].second = pos[j];
    j = 2 * i + 1;
    while (pos[j] == -1) {
      if (tree2[2 * i + 2].second > tree2[2 * j + 1].first)
        j = 2 * j + 1;
      else
        j = 2 * j + 2;
    }
    inter[i].first = pos[j];
  }
  return 0;
}
int build2(int s, int e, int i) {
  if (s == e) {
    tree2[i] = make_pair(a[s], a[s]), pos[i] = s;
    return 0;
  }
  int mid = (s + e) / 2;
  build2(s, mid, 2 * i + 1), build2(mid + 1, e, 2 * i + 2);
  tree2[i] = com(tree2[2 * i + 1], tree2[2 * i + 2]), pos[i] = -1;
  getInter(s, e, i);
  if (inter[i] != make_pair(-1, -1)) update(inter[i].first, inter[i].second, 1);
  return 0;
}
int update2(int s, int e, int ai, int i, int num) {
  if ((s > ai) || (e < ai))
    return 0;
  else if (s == e) {
    tree2[i] = make_pair(num, num);
    return 0;
  }
  int mid = (s + e) / 2;
  update2(s, mid, ai, 2 * i + 1, num), update2(mid + 1, e, ai, 2 * i + 2, num);
  tree2[i] = com(tree2[2 * i + 1], tree2[2 * i + 2]);
  if (inter[i] != make_pair(-1, -1))
    update(inter[i].first, inter[i].second, -1);
  getInter(s, e, i);
  if (inter[i] != make_pair(-1, -1)) update(inter[i].first, inter[i].second, 1);
  return 0;
}
int main() {
  int i;
  int q, p, x;
  scanf("%d %d", &n, &q);
  for (i = 0; i < n; i++) scanf("%d", &a[i]);
  build(), build2(0, n - 1, 0);
  for (i = 0; i < q; i++) {
    scanf("%d %d", &p, &x), p--, a[p] = x;
    update2(0, n - 1, p, 0, x);
    printf("%d\n", occ[1]);
  }
  return 0;
}
