#include <bits/stdc++.h>
using namespace std;
const int V = 1000000;
int n, q, x, y, z, a[500005];
int val[V << 2 | 4], minn[V << 2 | 4], num[V << 2 | 4], tag[V << 2 | 4];
inline void pushup(int u) {
  if (minn[u << 1] == minn[u << 1 | 1]) {
    minn[u] = minn[u << 1];
    num[u] = num[u << 1] + num[u << 1 | 1];
    return;
  }
  int t = minn[u << 1] < minn[u << 1 | 1] ? u << 1 : u << 1 | 1;
  minn[u] = minn[t];
  num[u] = num[t];
}
void build(int u, int l, int r) {
  if (l == r) {
    minn[u] = 0x3f3f3f3f;
    num[u] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(u << 1, l, mid);
  build(u << 1 | 1, mid + 1, r);
  pushup(u);
}
inline void calc(int u, int z) {
  val[u] += z;
  minn[u] += z;
  tag[u] += z;
}
inline void pushdown(int u) {
  if (tag[u]) {
    calc(u << 1, tag[u]);
    calc(u << 1 | 1, tag[u]);
    tag[u] = 0;
  }
}
void add(int u, int l, int r, int x, int y, int z) {
  if (x <= l && r <= y) {
    calc(u, z);
    return;
  }
  pushdown(u);
  int mid = (l + r) >> 1;
  if (x <= mid) add(u << 1, l, mid, x, y, z);
  if (y > mid) add(u << 1 | 1, mid + 1, r, x, y, z);
  pushup(u);
}
void modi(int u, int l, int r, int x) {
  if (l == r) {
    if (minn[u] < 1e8)
      minn[u] = 0x3f3f3f3f;
    else
      minn[u] = val[u];
    return;
  }
  pushdown(u);
  int mid = (l + r) >> 1;
  if (x <= mid)
    modi(u << 1, l, mid, x);
  else
    modi(u << 1 | 1, mid + 1, r, x);
  pushup(u);
}
int main() {
  scanf("%d%d", &n, &q);
  build(1, 1, V);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    if (i > 1 && a[i - 1] < a[i]) add(1, 1, V, a[i - 1], a[i] - 1, 1);
    modi(1, 1, V, a[i]);
  }
  while (q--) {
    scanf("%d%d", &x, &y);
    if (x > 1 && a[x - 1] < a[x]) add(1, 1, V, a[x - 1], a[x] - 1, -1);
    if (x < n && a[x] < a[x + 1]) add(1, 1, V, a[x], a[x + 1] - 1, -1);
    z = a[x], a[x] = y;
    if (x > 1 && a[x - 1] < a[x]) add(1, 1, V, a[x - 1], a[x] - 1, 1);
    if (x < n && a[x] < a[x + 1]) add(1, 1, V, a[x], a[x + 1] - 1, 1);
    modi(1, 1, V, z), modi(1, 1, V, y);
    printf("%d\n", minn[1] < 1e8 ? num[1] : 1);
  }
  return 0;
}
