#include <bits/stdc++.h>
using namespace std;
int gi() {
  int res = 0, w = 1;
  char ch = getchar();
  while (ch != '-' && !isdigit(ch)) ch = getchar();
  if (ch == '-') w = -1, ch = getchar();
  while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
  return res * w;
}
const int MAX_N = 1e6 + 5;
const int V = 1e6 + 1;
int mn[MAX_N << 2], tag[MAX_N << 2], cnt[MAX_N << 2];
void pushup(int o) {
  mn[o] = min(mn[(o << 1)], mn[(o << 1 | 1)]), cnt[o] = 0;
  if (mn[(o << 1)] == mn[o]) cnt[o] += cnt[(o << 1)];
  if (mn[(o << 1 | 1)] == mn[o]) cnt[o] += cnt[(o << 1 | 1)];
}
void puttag(int o, int v) { tag[o] += v, mn[o] += v; }
void pushdown(int o) {
  if (!tag[o]) return;
  puttag((o << 1), tag[o]), puttag((o << 1 | 1), tag[o]);
  tag[o] = 0;
}
void modify(int o, int l, int r, int ql, int qr, int v) {
  if (ql <= l && r <= qr) return puttag(o, v);
  pushdown(o);
  int mid = (l + r) >> 1;
  if (ql <= mid) modify((o << 1), l, mid, ql, qr, v);
  if (qr > mid) modify((o << 1 | 1), mid + 1, r, ql, qr, v);
  pushup(o);
}
void mdy(int o, int l, int r, int pos, int v) {
  if (l == r) return (void)(cnt[o] += v);
  pushdown(o);
  int mid = (l + r) >> 1;
  if (pos <= mid)
    mdy((o << 1), l, mid, pos, v);
  else
    mdy((o << 1 | 1), mid + 1, r, pos, v);
  pushup(o);
}
int query(int o, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return mn[o] == 1 ? cnt[o] : 0;
  pushdown(o);
  int mid = (l + r) >> 1, res = 0;
  if (ql <= mid) res = query((o << 1), l, mid, ql, qr);
  if (qr > mid) res += query((o << 1 | 1), mid + 1, r, ql, qr);
  return res;
}
void upd(int l, int r, int v) {
  if (l == r) return (void)puts("xgzc ak ioi");
  if (l > r) swap(l, r);
  modify(1, 0, V, l, r - 1, v);
}
int N, Q, a[MAX_N];
int main() {
  N = gi(), Q = gi();
  for (int i = 1; i <= N; i++) a[i] = gi();
  a[0] = V, a[N + 1] = 0;
  for (int i = 0; i <= N; i++) upd(a[i], a[i + 1], 1), mdy(1, 0, V, a[i], 1);
  while (Q--) {
    int p = gi(), v = gi();
    upd(a[p - 1], a[p], -1), upd(a[p], a[p + 1], -1), mdy(1, 0, V, a[p], -1);
    a[p] = v;
    upd(a[p - 1], a[p], 1), upd(a[p], a[p + 1], 1), mdy(1, 0, V, a[p], 1);
    printf("%d\n", query(1, 0, V, 1, V - 1));
  }
  return 0;
}
