#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int a[N], vis[2 * N];
pair<int, int> seg[8 * N];
int lz[8 * N];
void prop(int l, int r, int k) {
  if (l != r) {
    lz[k * 2] += lz[k];
    lz[k * 2 + 1] += lz[k];
  }
  seg[k].first += lz[k];
  lz[k] = 0;
}
pair<int, int> merge(pair<int, int>& x, pair<int, int>& y) {
  if (x.first < y.first)
    return x;
  else if (x.first > y.first)
    return y;
  return {x.first, x.second + y.second};
}
void build(int l, int r, int k) {
  if (l == r) {
    seg[k] = {1, vis[l]};
    return;
  }
  int m = (l + r) / 2;
  build(l, m, k * 2);
  build(m + 1, r, k * 2 + 1);
  seg[k] = merge(seg[k * 2], seg[k * 2 + 1]);
}
void upd(int l, int r, int k, int a, int b, int v) {
  if (lz[k] != 0) prop(l, r, k);
  if (b < l || r < a || a > b) return;
  if (a <= l && r <= b) {
    lz[k] = v;
    prop(l, r, k);
    return;
  }
  int m = (l + r) / 2;
  upd(l, m, k * 2, a, b, v);
  upd(m + 1, r, k * 2 + 1, a, b, v);
  seg[k] = merge(seg[k * 2], seg[k * 2 + 1]);
}
void ch(int l, int r, int k, int a) {
  if (lz[k] != 0) prop(l, r, k);
  if (a < l || r < a) return;
  if (a <= l && r <= a) {
    seg[k].second ^= 1;
    return;
  }
  int m = (l + r) / 2;
  ch(l, m, k * 2, a);
  ch(m + 1, r, k * 2 + 1, a);
  seg[k] = merge(seg[k * 2], seg[k * 2 + 1]);
}
void f(int x, int y, int l, int r) {
  int v = 2;
  if (x > y) {
    v *= -1;
    swap(x, y);
  }
  upd(1, 2 * N - 1, 1, x + 1, min(y, min(l, r)), -v);
  upd(1, 2 * N - 1, 1, max(x, max(l, r)) + 1, y, +v);
}
int main() {
  int n, q, ans = 0;
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    vis[a[i]] = 1;
  }
  build(1, 2 * N - 1, 1);
  a[0] = 2 * N - 1;
  for (int i = 1; i <= n; i++) f(0, a[i], a[i - 1], 0);
  while (q--) {
    int i, x;
    scanf("%d %d", &i, &x);
    f(a[i], x, a[i - 1], a[i + 1]);
    ch(1, 2 * N - 1, 1, a[i]);
    a[i] = x;
    ch(1, 2 * N - 1, 1, a[i]);
    printf("%d\n", seg[1].second);
  }
  return 0;
}
