#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool get_int(T &x) {
  char t = getchar();
  bool neg = false;
  x = 0;
  for (; (t > '9' || t < '0') && t != '-' && t != EOF; t = getchar())
    ;
  if (t == '-') neg = true, t = getchar();
  if (t == EOF) return false;
  for (; t <= '9' && t >= '0'; t = getchar()) x = x * 10 + t - '0';
  if (neg) x = -x;
  return true;
}
template <typename T>
void print_int(T x) {
  if (x < 0) putchar('-'), x = -x;
  short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
const int inf = 0x3f3f3f3f;
const long long Linf = 1ll << 61;
const double pi = acos(-1.0);
const int maxn = 500111;
const int maxv = 2100111;
namespace sgt {
int mn[maxv], mncnt[maxv], dlt[maxv];
void push(int t) {
  if (dlt[t]) {
    mn[(t << 1)] += dlt[t];
    dlt[(t << 1)] += dlt[t];
    mn[((t << 1) | 1)] += dlt[t];
    dlt[((t << 1) | 1)] += dlt[t];
    dlt[t] = 0;
  }
}
void pull(int t) {
  mn[t] = min(mn[(t << 1)], mn[((t << 1) | 1)]);
  mncnt[t] = 0;
  if (mn[(t << 1)] == mn[t]) mncnt[t] += mncnt[(t << 1)];
  if (mn[((t << 1) | 1)] == mn[t]) mncnt[t] += mncnt[((t << 1) | 1)];
}
void setv(int p, int v, int tl, int tr, int t) {
  if (tl == tr) {
    mncnt[t] = v;
    return;
  }
  push(t);
  int mid = (tl + tr) >> 1;
  if (p <= mid)
    setv(p, v, tl, mid, (t << 1));
  else
    setv(p, v, mid + 1, tr, ((t << 1) | 1));
  pull(t);
}
void modify(int l, int r, int v, int tl, int tr, int t) {
  if (l <= tl && tr <= r) {
    mn[t] += v;
    dlt[t] += v;
    return;
  }
  push(t);
  int mid = (tl + tr) >> 1;
  if (l <= mid) modify(l, r, v, tl, mid, (t << 1));
  if (r > mid) modify(l, r, v, mid + 1, tr, ((t << 1) | 1));
  pull(t);
}
int query() {
  if (mn[1] == 1)
    return mncnt[1];
  else
    return 0;
}
}  // namespace sgt
int MX = 1000001;
int n, q, a[maxn];
int main() {
  (get_int(n) && get_int(q));
  for (int i = 1; i <= n; i++) get_int(a[i]);
  a[0] = MX;
  a[n + 1] = 0;
  for (int i = 0; i <= n; i++)
    sgt::modify(min(a[i], a[i + 1]) + 1, max(a[i], a[i + 1]), 1, 1, MX, 1);
  for (int i = 1; i <= n; i++) sgt::setv(a[i] + 1, 1, 1, MX, 1);
  for (int i = 1, pos, v; i <= q; i++) {
    scanf("%d%d", &pos, &v);
    sgt::setv(a[pos] + 1, 0, 1, MX, 1);
    sgt::modify(min(a[pos - 1], a[pos]) + 1, max(a[pos - 1], a[pos]), -1, 1, MX,
                1);
    sgt::modify(min(a[pos], a[pos + 1]) + 1, max(a[pos], a[pos + 1]), -1, 1, MX,
                1);
    a[pos] = v;
    sgt::setv(a[pos] + 1, 1, 1, MX, 1);
    sgt::modify(min(a[pos - 1], a[pos]) + 1, max(a[pos - 1], a[pos]), 1, 1, MX,
                1);
    sgt::modify(min(a[pos], a[pos + 1]) + 1, max(a[pos], a[pos + 1]), 1, 1, MX,
                1);
    printf("%d\n", sgt::query());
  }
  return 0;
}
