#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
const int maxx = 1000005;
int n, x, y, q, l, r;
int a[N];
struct Tree {
  int ans, m, tag;
} tr[maxx * 6];
void pushdown(int rt) {
  int lson = rt << 1;
  int rson = rt << 1 | 1;
  tr[lson].m += tr[rt].tag;
  tr[rson].m += tr[rt].tag;
  tr[lson].tag += tr[rt].tag;
  tr[rson].tag += tr[rt].tag;
  tr[rt].tag = 0;
}
void updata(int rt) {
  int lson = rt << 1;
  int rson = rt << 1 | 1;
  if (tr[lson].m == tr[rson].m) {
    tr[rt].m = tr[lson].m;
    tr[rt].ans = tr[lson].ans + tr[rson].ans;
  } else if (tr[lson].m < tr[rson].m) {
    tr[rt].m = tr[lson].m;
    tr[rt].ans = tr[lson].ans;
  } else {
    tr[rt].m = tr[rson].m;
    tr[rt].ans = tr[rson].ans;
  }
}
void change(int rt, int l, int r, int cl, int cr, int C) {
  if (cl <= l && r <= cr) {
    tr[rt].m += C;
    tr[rt].tag += C;
    return;
  }
  pushdown(rt);
  int mid = (l + r) >> 1;
  if (cl <= mid) change(rt << 1, l, mid, cl, cr, C);
  if (cr > mid) change(rt << 1 | 1, mid + 1, r, cl, cr, C);
  updata(rt);
}
void change2(int rt, int l, int r, int x, int C) {
  if (l == r) {
    tr[rt].ans += C;
    return;
  }
  pushdown(rt);
  int mid = (l + r) >> 1;
  if (x <= mid) change2(rt << 1, l, mid, x, C);
  if (x > mid) change2(rt << 1 | 1, mid + 1, r, x, C);
  updata(rt);
}
int query(int rt, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    if (tr[rt].m == 1) return tr[rt].ans;
    return 0;
  }
  pushdown(rt);
  int mid = (l + r) >> 1, summ = 0;
  if (ql <= mid) summ += query(rt << 1, l, mid, ql, qr);
  if (qr > mid) summ += query(rt << 1 | 1, mid + 1, r, ql, qr);
  updata(rt);
  return summ;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  a[0] = maxx;
  a[n + 1] = 0;
  for (int i = 1; i <= n; ++i) change2(1, 0, maxx, a[i], 1);
  for (int i = 1; i <= n + 1; ++i) {
    int l = a[i - 1];
    int r = a[i];
    if (l == r) continue;
    if (l > r) swap(l, r);
    change(1, 0, maxx, l, r - 1, 1);
  }
  for (int i = 1; i <= q; ++i) {
    scanf("%d %d", &x, &y);
    l = a[x];
    r = a[x + 1];
    if (l != r) {
      if (l > r) swap(l, r);
      change(1, 0, maxx, l, r - 1, -1);
    }
    l = a[x - 1];
    r = a[x];
    if (l != r) {
      if (l > r) swap(l, r);
      change(1, 0, maxx, l, r - 1, -1);
    }
    change2(1, 0, maxx, a[x], -1);
    change2(1, 0, maxx, y, 1);
    a[x] = y;
    l = a[x];
    r = a[x + 1];
    if (l != r) {
      if (l > r) swap(l, r);
      change(1, 0, maxx, l, r - 1, 1);
    }
    l = a[x - 1];
    r = a[x];
    if (l != r) {
      if (l > r) swap(l, r);
      change(1, 0, maxx, l, r - 1, 1);
    }
    printf("%d\n", query(1, 0, maxx, 1, maxx - 1));
  }
  return 0;
}
