#include <bits/stdc++.h>
using namespace std;
inline int gi() {
  int f = 1, sum = 0;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    sum = (sum << 3) + (sum << 1) + ch - '0';
    ch = getchar();
  }
  return f * sum;
}
const int N = 500010, Inf = 1e6 + 1, M = Inf + 20;
int tag[M << 2], mn[M << 2], cnt[M << 2], n, Q, a[N];
void pushup(int o) {
  cnt[o] = 0;
  mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
  if (mn[o] == mn[o << 1]) cnt[o] += cnt[o << 1];
  if (mn[o] == mn[o << 1 | 1]) cnt[o] += cnt[o << 1 | 1];
}
void puttag(int o, int v) {
  mn[o] += v;
  tag[o] += v;
}
void pushdown(int o) {
  if (tag[o]) {
    puttag(o << 1, tag[o]);
    puttag(o << 1 | 1, tag[o]);
    tag[o] = 0;
  }
}
void modify(int o, int l, int r, int posl, int posr, int v) {
  if (posl <= l && r <= posr) {
    puttag(o, v);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(o);
  if (posl <= mid) modify(o << 1, l, mid, posl, posr, v);
  if (mid < posr) modify(o << 1 | 1, mid + 1, r, posl, posr, v);
  pushup(o);
}
void modify(int o, int l, int r, int pos, int v) {
  if (l == r) {
    cnt[o] += v;
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(o);
  if (pos <= mid)
    modify(o << 1, l, mid, pos, v);
  else
    modify(o << 1 | 1, mid + 1, r, pos, v);
  pushup(o);
}
int query(int o, int l, int r, int posl, int posr) {
  if (posl <= l && r <= posr) return mn[o] == 1 ? cnt[o] : 0;
  int mid = (l + r) >> 1, ret = 0;
  pushdown(o);
  if (posl <= mid) ret = query(o << 1, l, mid, posl, posr);
  if (mid < posr) ret += query(o << 1 | 1, mid + 1, r, posl, posr);
  pushup(o);
  return ret;
}
void modify(int l, int r, int v) {
  if (l == r) return;
  if (l > r) swap(l, r);
  modify(1, 0, Inf, l, r - 1, v);
}
int main() {
  n = gi();
  Q = gi();
  for (int i = 1; i <= n; i++) a[i] = gi();
  a[0] = Inf;
  a[n + 1] = 0;
  for (int i = 0; i <= n; i++)
    modify(a[i], a[i + 1], 1), modify(1, 0, Inf, a[i], 1);
  while (Q--) {
    int p = gi(), v = gi();
    modify(a[p - 1], a[p], -1);
    modify(a[p], a[p + 1], -1);
    modify(1, 0, Inf, a[p], -1);
    a[p] = v;
    modify(a[p - 1], a[p], 1);
    modify(a[p], a[p + 1], 1);
    modify(1, 0, Inf, a[p], 1);
    printf("%d\n", query(1, 0, Inf, 1, Inf - 1));
  }
  return 0;
}
