#include <bits/stdc++.h>
using namespace std;
namespace Fread {
const int MAXN = 1 << 20;
char buffer[MAXN], *S, *T;
inline char getchar() {
  if (S == T) {
    T = (S = buffer) + fread(buffer, 1, MAXN, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
}  // namespace Fread
inline int read() {
  int f = 1, x = 0;
  char ch = Fread::getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = Fread::getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = Fread::getchar();
  }
  return x * f;
}
inline long long readll() {
  long long f = 1, x = 0;
  char ch = Fread::getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = Fread::getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = Fread::getchar();
  }
  return x * f;
}
const int MAXN = 1e6 + 10, N = 1e6 + 1, INF = 0x3f3f3f3f;
int n, q, a[MAXN];
struct SegmentTree {
  int val[MAXN << 2], cnt[MAXN << 2], tag[MAXN << 2];
  void push_down(int p) {
    if (tag[p]) {
      val[p << 1] += tag[p];
      tag[p << 1] += tag[p];
      val[p << 1 | 1] += tag[p];
      tag[p << 1 | 1] += tag[p];
      tag[p] = 0;
    }
  }
  void push_up(int p) {
    if (val[p << 1] == val[p << 1 | 1]) {
      val[p] = val[p << 1];
      cnt[p] = cnt[p << 1] + cnt[p << 1 | 1];
    } else if (val[p << 1] < val[p << 1 | 1]) {
      val[p] = val[p << 1];
      cnt[p] = cnt[p << 1];
    } else {
      val[p] = val[p << 1 | 1];
      cnt[p] = cnt[p << 1 | 1];
    }
  }
  void modify1(int p, int l, int r, int ql, int qr, int x) {
    if (ql <= l && qr >= r) {
      tag[p] += x;
      val[p] += x;
      return;
    }
    push_down(p);
    int mid = (l + r) >> 1;
    if (ql <= mid) modify1(p << 1, l, mid, ql, qr, x);
    if (qr > mid) modify1(p << 1 | 1, mid + 1, r, ql, qr, x);
    push_up(p);
  }
  void modify2(int p, int l, int r, int pos, int x) {
    if (l == r) {
      cnt[p] += x;
      assert(cnt[p] < 2);
      return;
    }
    push_down(p);
    int mid = (l + r) >> 1;
    if (pos <= mid)
      modify2(p << 1, l, mid, pos, x);
    else
      modify2(p << 1 | 1, mid + 1, r, pos, x);
    push_up(p);
  }
  int query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) return val[p] == 1 ? cnt[p] : 0;
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res = query(p << 1, l, mid, ql, qr);
    if (qr > mid) res += query(p << 1 | 1, mid + 1, r, ql, qr);
    return res;
  }
  SegmentTree() {}
} T;
int main() {
  n = read();
  q = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  a[0] = N;
  a[n + 1] = 0;
  for (int i = 0; i <= n; ++i) {
    if (a[i] != a[i + 1])
      T.modify1(1, 0, N, min(a[i], a[i + 1]) + 1, max(a[i], a[i + 1]), 1);
    if (i) T.modify2(1, 0, N, a[i], 1);
  }
  while (q--) {
    int i = read(), x = read();
    T.modify2(1, 0, N, a[i], -1);
    if (a[i] != a[i - 1]) {
      T.modify1(1, 0, N, min(a[i], a[i - 1]) + 1, max(a[i], a[i - 1]), -1);
    }
    if (a[i] != a[i + 1]) {
      T.modify1(1, 0, N, min(a[i], a[i + 1]) + 1, max(a[i], a[i + 1]), -1);
    }
    a[i] = x;
    if (a[i] != a[i - 1]) {
      T.modify1(1, 0, N, min(a[i], a[i - 1]) + 1, max(a[i], a[i - 1]), 1);
    }
    if (a[i] != a[i + 1]) {
      T.modify1(1, 0, N, min(a[i], a[i + 1]) + 1, max(a[i], a[i + 1]), 1);
    }
    T.modify2(1, 0, N, a[i], 1);
    printf("%d\n", T.query(1, 0, N, 1, N - 1));
  }
  return 0;
}
