#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const int N = 1e5;
const int Q = 2.5e5;

int n, q;
int a[N + 5], las[N + 5];
pair<int, int> upd[N + Q + 5];
int pre[N + Q + 5], nxt[N + Q + 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 = 0, int r = 0, int h = 0, int w = 0): 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; }
};

pair<vector<node>, int> build(vector<int> newStatic, vector<pair<int, int>> upd, vector<node> tr) {
  sort(newStatic.begin(), newStatic.end()), sort(upd.begin(), upd.end());
  static int anc[N + 5];
  static node newTr[N + 5];
  int j = 0, top = 0, tot = 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[tot++] = tr[anc[top]];
      anc[++top] = j;
    }
    for (; top && tr[anc[top]].r < i; --top) newTr[tot++] = tr[anc[top]];
    for (; top && tr[anc[top]].h <= a[i]; --top);
  }
  for (; top; --top) newTr[tot++] = tr[anc[top]];
  for (; j < tr.size(); ++j) newTr[tot++] = tr[j];
  for (int i: newStatic) {
    int l = seg.queryL(i - 1, a[i]);
    if (l) newTr[tot++] = node(l, i, a[i], 1);
    int r = seg.queryR(i + 1, a[i]);
    if (r <= n) newTr[tot++] = node(i, r, a[i], 1);
  }
  tr = vector<node>(newTr, newTr + tot), sort(tr.begin(), tr.end()), tr.erase(unique(tr.begin(), tr.end()), tr.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;
  }
  vector<int> crit(1, 0);
  crit.reserve(upd.size() + 1);
  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]);
    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());
  crit.reserve(crit.size() * 2);
  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;
    }
    for (; top && tr[anc[top]].r <= tr[crit[i + 1]].r; --top);
    crit.push_back(anc[top]);
  }
  sort(crit.begin(), crit.end()), crit.erase(unique(crit.begin(), crit.end()), crit.end());
  top = 0;
  for (int i = 0; i < crit.size(); ++i) {
    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[i] = node(l, r, h, w);
  }
  return {vector<node>(newTr, newTr + crit.size()), cnt};
}

int ans[N + Q + 5];

void solve(int l, int r, vector<node> tr) {
  if (l == r) {
    a[upd[l].first] = upd[l].second;
    int tag = build({upd[l].first}, {}, tr).second;
    ans[l] += tag, ans[l + 1] -= tag;
    return ;
  }
  int mid = (l + r) >> 1;
  vector<int> tmp;
  vector<pair<int, int>> updTmp;
  static bool vis[N + 5];
  if (mid >= n) {
    for (int i = mid + 1; i <= r; ++i) if (pre[i] < l) tmp.push_back(upd[i].first), vis[upd[i].first] = 1;
    updTmp = vector<pair<int, int>>(upd + l, upd + mid + 1);
    for (int i = l; i <= mid; ++i) if (pre[i] && pre[i] < l && !vis[upd[pre[i]].first]) updTmp.push_back(upd[pre[i]]);
    for (int i: tmp) vis[i] = 0;
    auto [L, lTag] = build(tmp, updTmp, tr);
    ans[l] += lTag, ans[mid + 1] -= lTag;
    vector<int>().swap(tmp), vector<pair<int, int>>().swap(updTmp);
    solve(l, mid, L);
  }
  for (int i = l; i <= mid; ++i) if (nxt[i] > r) tmp.push_back(upd[i].first), vis[upd[i].first] = 1;
  updTmp = vector<pair<int, int>>(upd + mid + 1, upd + r + 1);
  for (int i = mid + 1; i <= r; ++i) if (pre[i] && pre[i] <= mid && !vis[upd[pre[i]].first]) updTmp.push_back(upd[pre[i]]);
  for (int i: tmp) vis[i] = 0;
  auto [R, rTag] = build(tmp, updTmp, tr);
  ans[mid + 1] += rTag, ans[r + 1] -= rTag;
  solve(mid + 1, r, R);
}

int main() {
  scanf("%d%d", &n, &q);
  a[0] = a[n + 1] = inf;
  for (int i = 1; i <= n; ++i)
    scanf("%d", a + i),
    upd[i] = make_pair(i, a[i]), las[i] = i;
  for (int i = n + 1; i <= n + q; ++i)
    scanf("%d%d", &upd[i].first, &upd[i].second),
    pre[i] = las[upd[i].first], las[upd[i].first] = i;
  fill(las + 1, las + n + 1, n + q + 1);
  for (int i = n + q; i; --i) nxt[i] = las[upd[i].first], las[upd[i].first] = i;
  solve(1, n + q, {node(0, n + 1, inf, 0)});
  for (int i = 1; i <= n + q; ++i) ans[i] += ans[i - 1];
  for (int i = n; i <= n + q; ++i) printf("%d\n", ans[i]);
}