#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const int N = 1e5;

int n, q;
int a[N + 5];
pair<int, int> upd[N + 5];

struct SegmentTree {
  #define ls (u << 1)
  #define rs (ls | 1)
  int seg[N * 4 + 5];
  void insert(int x, int k, int u, int tl, int tr) {
    if (tl == tr) { seg[u] = k; return ; }
    int mid = (tl + tr) >> 1;
    if (x <= mid) insert(x, k, ls, tl, mid);
    else insert(x, k, rs, mid + 1, tr);
    seg[u] = max(seg[ls], seg[rs]);
  }
  void insert(int x, int k) { insert(x, k, 1, 1, n); }
  pair<int, int> queryL(int x, int k, int u, int tl, int tr) {
    if (seg[u] < k) return {0, inf};
    if (tl == tr) return {tl, seg[u]};
    int mid = (tl + tr) >> 1;
    if (x <= mid) return queryL(x, k, ls, tl, mid);
    auto ret = queryL(x, k, rs, mid + 1, tr);
    if (!ret.first) ret = queryL(x, k, ls, tl, mid);
    return ret;
  }
  int queryL(int x, int k) {
    if (!x) return 0;
    auto res = queryL(x, k, 1, 1, n);
    return res.second == k ? res.first : 0;
  }
  pair<int, int> queryR(int x, int k, int u, int tl, int tr) {
    if (seg[u] < k) return {n + 1, inf};
    if (tl == tr) return {tl, seg[u]};
    int mid = (tl + tr) >> 1;
    if (x > mid) return queryR(x, k, rs, mid + 1, tr);
    auto ret = queryR(x, k, ls, tl, mid);
    if (ret.first > n) ret = queryR(x, k, rs, mid + 1, tr);
    return ret;
  }
  int queryR(int x, int k) {
    if (x > n) return n + 1;
    auto res = queryR(x, k, 1, 1, n);
    return res.second == k ? res.first : n + 1;
  }
  #undef ls
  #undef rs
} seg;

struct node {
  int l, r, h, w;
  node(int l, int r, int h, int w): l(l), r(r), h(h), w(w) {}
  bool operator<(const node &o) const { return l < o.l; }
  bool operator>(const node &o) const { return l > o.l; }
  bool operator==(const node &o) const { return l == o.l; }
};

bool FLAG;

pair<vector<node>, int> build(set<int> newStatic, vector<pair<int, int>> upd, vector<node> tr) {
  /*printf("newStatic = { ");
  for (int i: newStatic) printf("%d ", i);
  puts("}");*/
  /*if (FLAG) {
    puts("BEGIN");
    for (int i = 0; i < tr.size(); ++i) printf("%d %d %d %d\n", tr[i].l, tr[i].r, tr[i].h, tr[i].w);
    puts("END");
  }*/
  static int anc[N + 5];
  int top = 0;
  vector<node> newTr;
  int j = 0;
  for (auto [i, _]: upd) seg.insert(i, 0);
  for (int i: newStatic) {
    seg.insert(i, a[i]);
    for (; j < tr.size() && tr[j].l <= i; ++j) {
      auto [l, r, h, w] = tr[j];
      for (; top && tr[anc[top]].r <= r; --top) newTr.push_back(tr[anc[top]]);
      anc[++top] = j;
    }
    for (; top && tr[anc[top]].r < i; --top) newTr.push_back(tr[anc[top]]);
    //if (FLAG) printf("%d\n", top);
    for (; top && tr[anc[top]].h <= a[i]; --top) tr[anc[top]].w = -1;
    //if (FLAG) printf("%d\n", top);
  }
  for (; top; --top) newTr.push_back(tr[anc[top]]);
  for (; j < tr.size(); ++j) newTr.push_back(tr[j]);
  for (int i: newStatic) {
    int l = seg.queryL(i - 1, a[i]);
    /*if (newStatic.size() == 1 && newStatic.count(4) && upd.size() == 1)
      printf("%d %d %d\n", i, a[i], l);*/
    if (l && !newStatic.count(l)) newTr.emplace_back(l, i, a[i], 1);
    int r = seg.queryR(i + 1, a[i]);
    /*if (newStatic.size() == 1 && newStatic.count(4) && upd.size() == 1)
      printf("%d %d %d\n", i, a[i], r);*/
    if (r <= n) newTr.emplace_back(i, r, a[i], 1);
  }
  // for (auto [i, _]: upd) newTr.emplace_back(i, i, 0, 0);
  tr = newTr, sort(tr.begin(), tr.end());
  /*if (FLAG) {
    puts("BEGIN");
    for (int i = 0; i < tr.size(); ++i) printf("%d %d %d %d\n", tr[i].l, tr[i].r, tr[i].h, tr[i].w);
    puts("END");
  }*/
  vector<int> sum(tr.size());
  int cnt = 0;
  for (int i = 0; i < tr.size(); ++i) {
    auto [l, r, h, w] = tr[i];
    for (; top && tr[anc[top]].r <= r; --top);
    if (top) sum[i] = sum[anc[top]];
    sum[i] += w, cnt += w;
    anc[++top] = i;
  }
  //if (FLAG) printf("CNT %d\n", cnt);
  vector<int> crit(1, 0);
  sort(upd.begin(), upd.end());
  j = top = 0;
  for (auto [i, h]: upd) {
    for (; j < tr.size() && tr[j].l <= i; ++j) {
      auto [l, r, h, w] = tr[j];
      for (; top && tr[anc[top]].r <= r; --top);
      anc[++top] = j;
    }
    for (; top && tr[anc[top]].r < i; --top);
    crit.push_back(anc[top]);
    //printf("%d %d, %d %d %d %d\n", i, h, tr[anc[top]].l, tr[anc[top]].r, tr[anc[top]].h, tr[anc[top]].w);
    int l = 1, r = top, mid, res = 1;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (tr[anc[mid]].h > h) l = mid + 1, res = mid;
      else r = mid - 1;
    }
    crit.push_back(anc[res]);
  }
  sort(crit.begin(), crit.end()), crit.erase(unique(crit.begin(), crit.end()), crit.end());
  //for (int i: crit) printf("%d %d %d %d\n", tr[i].l, tr[i].r, tr[i].h, tr[i].w);
  //puts("FUCK");
  j = top = 0;
  for (int i = 0, siz = crit.size(); i + 1 < siz; ++i) {
    for (; j <= crit[i]; ++j) {
      auto [l, r, h, w] = tr[j];
      for (; top && tr[anc[top]].r <= r; --top);
      anc[++top] = j;
    }
    int l = 1, r = top, mid, res = 1;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (tr[anc[mid]].r > tr[crit[i + 1]].r) l = mid + 1, res = mid;
      else r = mid - 1;
    }
    crit.push_back(anc[res]);
  }
  sort(crit.begin(), crit.end()), crit.erase(unique(crit.begin(), crit.end()), crit.end());
  vector<node>().swap(newTr), top = 0;
  for (int i = 0; i < crit.size(); ++i) {
    //if (newStatic.empty()) printf("%d, %d\n", crit[i], tr.size());
    auto [l, r, h, w] = tr[crit[i]];
    for (; top && tr[anc[top]].r <= r; --top);
    w = sum[crit[i]];
    if (top) w -= sum[anc[top]];
    cnt -= w; 
    anc[++top] = crit[i];
    newTr.emplace_back(l, r, h, w);
  }
  /*if (FLAG) {
    puts("BEGIN");
    for (int i = 0; i < newTr.size(); ++i) printf("%d %d %d %d\n", newTr[i].l, newTr[i].r, newTr[i].h, newTr[i].w);
    puts("END");
  }*/
  //if (FLAG) printf("CNT %d\n", cnt);
  //if (newStatic.empty()) puts("fuck here");
  return {newTr, cnt};
}

int ans[N + 5];

void solve(int l, int r, vector<node> tr) {
  //printf("D&C [%d, %d]\n", l, r);
  //for (auto i: tr) printf("%d %d %d %d\n", i.l, i.r, i.h, i.w);
  if (l == r) {
    //if (l == 3) printf("%d\n", ans[l]);
    if (l)
      a[upd[l].first] = upd[l].second,
      ans[l] += build({upd[l].first}, {}, tr).second;
    return ;
  }
  int mid = (l + r) >> 1;
  set<int> s, tmp;
  for (int i = max(l, 1); i <= r; ++i) s.insert(upd[i].first);
  tmp = s;
  for (int i = max(l, 1); i <= mid; ++i) tmp.erase(upd[i].first);
  //if (l == 3 && mid == 4) FLAG = 1;
  auto [L, lTag] = build(tmp, vector<pair<int, int>>(upd + max(l, 1), upd + mid + 1), tr);
  //printf("{ [%d, %d] } [%d, %d], with tag %d\n", l, mid, mid + 1, r, lTag);
  //if (l == 3 && mid == 4) FLAG = 0;
  for (int i = l; i <= mid; ++i) ans[i] += lTag;
  solve(l, mid, L);
  //for (int i: tmp) seg.insert(i, 0);
  tmp = s;
  for (int i = mid + 1; i <= r; ++i) tmp.erase(upd[i].first);
  //printf("ready to build [%d, %d]\n", mid + 1, r);
  auto [R, rTag] = build(tmp, vector<pair<int, int>>(upd + mid + 1, upd + r + 1), tr);
  //printf("[%d, %d] { [%d, %d] }, with tag %d\n", l, mid, mid + 1, r, rTag);
  for (int i = mid + 1; i <= r; ++i) ans[i] += rTag;
  solve(mid + 1, r, R);
  //for (int i: tmp) seg.insert(i, 0);
}

int main() {
  scanf("%d%d", &n, &q);
  set<int> tmp;
  for (int i = 1; i <= n; ++i) scanf("%d", a + i), tmp.insert(i);
  a[0] = a[n + 1] = inf;
  for (int i = 1; i <= q; ++i) scanf("%d%d", &upd[i].first, &upd[i].second), tmp.erase(upd[i].first);
  auto [tr, tag] = build(tmp, vector<pair<int, int>>(upd + 1, upd + q + 1), {node(0, n + 1, inf, 0)});
  for (int i = 0; i <= q; ++i) ans[i] += tag;
  //for (auto i: tr) printf("%d %d %d %d\n", i.l, i.r, i.h, i.w);
  solve(0, q, tr);
  for (int i = 0; i <= q; ++i) printf("%d\n", ans[i]);
}