#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int n, q, root = 1;
int a[1000010], mn[4000010], val[4000010], tag[4000010];
void pushup(int cur) {
  if (mn[(cur << 1)] < mn[(cur << 1 | 1)])
    mn[cur] = mn[(cur << 1)], val[cur] = val[(cur << 1)];
  else if (mn[(cur << 1)] > mn[(cur << 1 | 1)])
    mn[cur] = mn[(cur << 1 | 1)], val[cur] = val[(cur << 1 | 1)];
  else
    mn[cur] = mn[(cur << 1)], val[cur] = val[(cur << 1)] + val[(cur << 1 | 1)];
}
void pushtag(int cur, int v) { mn[cur] += v, tag[cur] += v; }
void pushdown(int cur) {
  if (!tag[cur]) return;
  pushtag((cur << 1), tag[cur]), pushtag((cur << 1 | 1), tag[cur]),
      tag[cur] = 0;
}
void update(int l, int r, int pos, int v, int cur) {
  if (l == r) {
    val[cur] += v;
    return;
  }
  pushdown(cur);
  if (pos <= ((l + r) >> 1))
    update(l, ((l + r) >> 1), pos, v, (cur << 1));
  else
    update(((l + r) >> 1) + 1, r, pos, v, (cur << 1 | 1));
  pushup(cur);
}
void modify(int L, int R, int l, int r, int v, int cur) {
  if (L > R) return;
  if (L <= l && R >= r) {
    pushtag(cur, v);
    return;
  }
  pushdown(cur);
  if (L <= ((l + r) >> 1)) modify(L, R, l, ((l + r) >> 1), v, (cur << 1));
  if (R > ((l + r) >> 1))
    modify(L, R, ((l + r) >> 1) + 1, r, v, (cur << 1 | 1));
  pushup(cur);
}
int query(int L, int R, int l, int r, int cur) {
  if (L <= l && R >= r) return mn[cur] == 1 ? val[cur] : 0;
  int v = 0;
  pushdown(cur);
  if (L <= ((l + r) >> 1)) v += query(L, R, l, ((l + r) >> 1), (cur << 1));
  if (R > ((l + r) >> 1))
    v += query(L, R, ((l + r) >> 1) + 1, r, (cur << 1 | 1));
  return v;
}
int main() {
  read(n), read(q), a[0] = 1000001;
  for (int i = 1; i <= n; ++i) read(a[i]), update(0, 1000001, a[i], 1, root);
  for (int i = 0; i <= n; ++i)
    modify(min(a[i], a[i + 1]), max(a[i], a[i + 1]) - 1, 0, 1000001, 1, root);
  while (q--) {
    int x;
    read(x), update(0, 1000001, a[x], -1, root);
    modify(min(a[x], a[x + 1]), max(a[x], a[x + 1]) - 1, 0, 1000001, -1, root);
    modify(min(a[x - 1], a[x]), max(a[x - 1], a[x]) - 1, 0, 1000001, -1, root);
    read(a[x]), update(0, 1000001, a[x], 1, root);
    modify(min(a[x], a[x + 1]), max(a[x], a[x + 1]) - 1, 0, 1000001, 1, root);
    modify(min(a[x - 1], a[x]), max(a[x - 1], a[x]) - 1, 0, 1000001, 1, root);
    printf("%d\n", query(1, 1000001 - 1, 0, 1000001, root));
  }
  return 0;
}
