#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 7;
const int inf = 1e7;
const long long inff = 1e18;
const long long mod = 1e9 + 7;
const int N = 1e6 + 4;
int a[maxn];
pair<int, int> seg[maxn * 8];
int tag[maxn * 8];
void push(int now, int l, int r) {
  if (l == r) {
    tag[now] = 0;
    return;
  }
  seg[now * 2].first += tag[now];
  seg[now * 2 + 1].first += tag[now];
  tag[now * 2] += tag[now];
  tag[now * 2 + 1] += tag[now];
  tag[now] = 0;
}
pair<int, int> pull(pair<int, int> x, pair<int, int> y) {
  if (x.first == y.first)
    return make_pair(x.first, x.second + y.second);
  else if (x.first > y.first)
    return y;
  else
    return x;
}
void Build(int now, int l, int r) {
  if (l == r) {
    seg[now] = make_pair(0, 1);
    return;
  }
  int m = (l + r) >> 1;
  Build(now * 2, l, m);
  Build(now * 2 + 1, m + 1, r);
  seg[now] = pull(seg[now * 2], seg[now * 2 + 1]);
}
void modify(int now, int l, int r, int ql, int qr, int v) {
  if (l >= ql && r <= qr) {
    seg[now].first += v;
    tag[now] += v;
    return;
  }
  int m = (l + r) >> 1;
  push(now, l, r);
  if (ql <= m) modify(now * 2, l, m, ql, qr, v);
  if (qr > m) modify(now * 2 + 1, m + 1, r, ql, qr, v);
  seg[now] = pull(seg[now * 2], seg[now * 2 + 1]);
}
int used[1000007];
void Modifys(int i, int x, int mode) {
  if (mode == 0)
    modify(1, 1, N, min(a[i], a[i - 1]) + 1, max(a[i], a[i - 1]), 1);
  else {
    modify(1, 1, N, a[i] + 1, a[i] + 1, inf);
    modify(1, 1, N, min(a[i], a[i - 1]) + 1, max(a[i], a[i - 1]), -1);
    modify(1, 1, N, min(a[i], a[i + 1]) + 1, max(a[i], a[i + 1]), -1);
    a[i] = x;
    modify(1, 1, N, a[i] + 1, a[i] + 1, -inf);
    modify(1, 1, N, min(a[i], a[i - 1]) + 1, max(a[i], a[i - 1]), 1);
    modify(1, 1, N, min(a[i], a[i + 1]) + 1, max(a[i], a[i + 1]), 1);
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  a[0] = 10000001, a[n + 1] = 0;
  for (int i = 1; i <= n; i++) cin >> a[i], used[a[i]] = 1;
  Build(1, 1, N);
  for (int i = 1; i <= n + 1; i++) Modifys(i, 0, 0);
  for (int i = 1; i <= N; i++)
    if (!used[i - 1]) modify(1, 1, N, i, i, inf);
  while (q--) {
    int pos, x;
    cin >> pos >> x;
    Modifys(pos, x, 1);
    assert(seg[1].first == 1);
    cout << seg[1].second << '\n';
  }
}
