#include <bits/stdc++.h>
using namespace std;
const int mxN = 5e5;
int n, q, a[mxN + 2], lz[1 << 21];
array<int, 2> st[1 << 21];
void app(int i, int x) {
  st[i][0] += x;
  lz[i] += x;
}
void psh(int i) {
  app(2 * i, lz[i]);
  app(2 * i + 1, lz[i]);
  lz[i] = 0;
}
void cmb(int i) {
  st[i] = st[2 * i][0] ^ st[2 * i + 1][0]
              ? min(st[2 * i], st[2 * i + 1])
              : array<int, 2>{st[2 * i][0], st[2 * i][1] + st[2 * i + 1][1]};
}
void upd1(int l1, int r1, int x, int i = 1, int l2 = 1, int r2 = 1e6 + 1) {
  if (l1 <= l2 && r2 <= r1) {
    app(i, x);
    return;
  }
  int m2 = (l2 + r2) / 2;
  psh(i);
  if (l1 <= m2) upd1(l1, r1, x, 2 * i, l2, m2);
  if (m2 < r1) upd1(l1, r1, x, 2 * i + 1, m2 + 1, r2);
  cmb(i);
}
void upd2(int l1, int x, int i = 1, int l2 = 1, int r2 = 1e6 + 1) {
  if (l2 == r2) {
    st[i][1] = x;
    return;
  }
  int m2 = (l2 + r2) / 2;
  psh(i);
  if (l1 <= m2)
    upd2(l1, x, 2 * i, l2, m2);
  else
    upd2(l1, x, 2 * i + 1, m2 + 1, r2);
  cmb(i);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  a[0] = 1e6 + 1;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    upd1(min(a[i - 1], a[i]) + 1, max(a[i - 1], a[i]), 1);
    upd2(a[i], 1);
  }
  upd1(1, a[n], 1);
  for (int i, x; q--;) {
    cin >> i >> x;
    upd2(a[i], 0);
    upd1(min(a[i - 1], a[i]) + 1, max(a[i - 1], a[i]), -1);
    upd1(min(a[i], a[i + 1]) + 1, max(a[i], a[i + 1]), -1);
    upd2(x, 1);
    upd1(min(a[i - 1], x) + 1, max(a[i - 1], x), 1);
    upd1(min(x, a[i + 1]) + 1, max(x, a[i + 1]), 1);
    a[i] = x;
    cout << st[1][1] << "\n";
  }
}
