#include <bits/stdc++.h>
using namespace std;
namespace thecold {
inline int read() {
  int res = 0;
  bool flag = false;
  char c = getchar();
  while (!isdigit(c)) flag = (c == '-'), c = getchar();
  while (isdigit(c)) res = res * 10 + (c ^ 48), c = getchar();
  return !flag ? res : -res;
}
const int Max_n = 1e6 + 5;
struct node {
  int l, r, val, tag, cnt, tmp;
  node(int a, int b) { l = a, r = b, tag = val = cnt = tmp = 0; }
  node() {}
} tree[Max_n << 2];
bool vis[Max_n];
int n, q, a[Max_n];
inline void push_up(const int tr) {
  if (tree[tr * 2].val < tree[tr * 2 + 1].val)
    tree[tr].val = tree[tr * 2].val, tree[tr].cnt = tree[tr * 2].cnt,
    tree[tr].tmp = tree[tr * 2].tmp;
  else if (tree[tr * 2 + 1].val < tree[tr * 2].val)
    tree[tr].val = tree[tr * 2 + 1].val, tree[tr].cnt = tree[tr * 2 + 1].cnt,
    tree[tr].tmp = tree[tr * 2 + 1].tmp;
  else
    tree[tr].val = tree[tr * 2].val,
    tree[tr].cnt = tree[tr * 2].cnt + tree[tr * 2 + 1].cnt,
    tree[tr].tmp = tree[tr * 2].tmp | tree[tr * 2 + 1].tmp;
}
void build(const int l, const int r, const int tr) {
  tree[tr] = node(l, r);
  if (l == r) {
    tree[tr].cnt = vis[l];
    if (vis[l]) tree[tr].tmp = 1 << l;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, tr * 2), build(mid + 1, r, tr * 2 + 1), push_up(tr);
}
inline void push_down(const int tr) {
  if (!tree[tr].tag) return;
  int tag = tree[tr].tag;
  tree[tr * 2].tag += tag, tree[tr * 2 + 1].tag += tag;
  tree[tr * 2].val += tag, tree[tr * 2 + 1].val += tag;
  tree[tr].tag = 0;
}
void change(const int l, const int r, const int tr, const int val) {
  if (l > r) return;
  int ll = tree[tr].l, rr = tree[tr].r;
  if (ll > r || rr < l) return;
  if (l <= ll && rr <= r)
    return tree[tr].tag += val, tree[tr].val += val, void();
  push_down(tr);
  change(l, r, tr * 2, val), change(l, r, tr * 2 + 1, val);
  push_up(tr);
}
void del(const int pos, const int tr) {
  int ll = tree[tr].l, rr = tree[tr].r;
  if (ll == rr) return tree[tr].cnt = 0, tree[tr].tmp = 0, void();
  int mid = (ll + rr) >> 1;
  push_down(tr);
  if (mid >= pos)
    del(pos, tr * 2);
  else
    del(pos, tr * 2 + 1);
  push_up(tr);
}
void add(const int pos, const int tr) {
  int ll = tree[tr].l, rr = tree[tr].r;
  if (ll == rr) return tree[tr].cnt = 1, tree[tr].tmp = 1 << pos, void();
  int mid = (ll + rr) >> 1;
  push_down(tr);
  if (mid >= pos)
    add(pos, tr * 2);
  else
    add(pos, tr * 2 + 1);
  push_up(tr);
}
inline void main() {
  n = read(), q = read();
  for (int i = 1; i <= n; ++i) vis[a[i] = read()] = true;
  build(1, 1e6, 1);
  change(a[1], 1e6, 1, 1);
  change(1, a[n] - 1, 1, 1);
  for (int i = 1; i < n; ++i)
    change(min(a[i], a[i + 1]), max(a[i], a[i + 1]) - 1, 1, 1);
  while (q--) {
    int pos = read(), val = read();
    if (pos == 1) {
      del(a[1], 1), change(a[1], 1e6, 1, -1),
          change(min(a[1], a[2]), max(a[1], a[2]) - 1, 1, -1);
      add(a[1] = val, 1), change(a[1], 1e6, 1, 1),
          change(min(a[1], a[2]), max(a[1], a[2]) - 1, 1, 1);
    } else if (pos == n) {
      del(a[n], 1), change(1, a[n] - 1, 1, -1),
          change(min(a[n - 1], a[n]), max(a[n - 1], a[n]) - 1, 1, -1);
      add(a[n] = val, 1), change(1, a[n] - 1, 1, 1),
          change(min(a[n - 1], a[n]), max(a[n - 1], a[n]) - 1, 1, 1);
    } else {
      del(a[pos], 1),
          change(min(a[pos - 1], a[pos]), max(a[pos - 1], a[pos]) - 1, 1, -1),
          change(min(a[pos + 1], a[pos]), max(a[pos + 1], a[pos]) - 1, 1, -1);
      add(a[pos] = val, 1),
          change(min(a[pos - 1], a[pos]), max(a[pos - 1], a[pos]) - 1, 1, 1),
          change(min(a[pos + 1], a[pos]), max(a[pos + 1], a[pos]) - 1, 1, 1);
    }
    printf("%d\n", tree[1].cnt);
  }
}
}  // namespace thecold
int main() {
  thecold::main();
  return 0;
}
