// Author: Klay Thompson
// Problem: I. Streetlights
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 250010;
const int inf = 1e9;

struct node {
  int amn, amn2, bmx, bmx2;
  node() { amn2 = inf, bmx2 = -inf; }
  node(int x, int y) { amn = x, bmx = y, amn2 = inf, bmx2 = -inf; }
  friend node operator+(node x, node y) {
    node res;
    res.amn = min(x.amn, y.amn);
    if (x.amn != res.amn) chkmn(res.amn2, x.amn);
    else chkmn(res.amn2, x.amn2);
    if (y.amn != res.amn) chkmn(res.amn2, y.amn);
    else chkmn(res.amn2, y.amn2);
    res.bmx = max(x.bmx, y.bmx);
    if (x.bmx != res.bmx) chkmx(res.bmx2, x.bmx);
    else chkmx(res.bmx2, x.bmx2);
    if (y.bmx != res.bmx) chkmx(res.bmx2, y.bmx);
    else chkmx(res.bmx2, y.bmx2);
    return res;
  }
} t[maxn << 2];

int n, m, tot, a[maxn], c[maxn], A[maxn], B[maxn], C[maxn], lz[maxn << 2], lmx[maxn], rmn[maxn];
vector<pii> av[maxn];
vector<int> res;

#define mid ((l + r) >> 1)

void build(int c, int l, int r, int x, int y) {
  lz[c] = 0;
  if (l == r) return t[c] = node(x, y), void();
  build(c << 1, l, mid, x, y), build(c << 1 | 1, mid + 1, r, x, y);
  t[c] = t[c << 1] + t[c << 1 | 1];
}

void upd(int, int, int, int, int, int, int, int);

void down(int c, int l, int r) {
  upd(c << 1, l, mid, l, mid, t[c].amn, t[c].bmx, lz[c]);
  upd(c << 1 | 1, mid + 1, r, mid + 1, r, t[c].amn, t[c].bmx, lz[c]);
  lz[c] = 0;
}

void upd(int c, int l, int r, int x, int y, int p, int q, int lv) {
  if (p <= t[c].amn && q >= t[c].bmx) return;
  if (l == x && r == y) {
    if (p <= t[c].amn && q >= t[c].bmx2) {
      return t[c].bmx = q, void();
    }
    if (q >= t[c].bmx && p <= t[c].amn2) {
      return t[c].amn = p, void();
    }
    if (p <= t[c].amn2 && q >= t[c].bmx2) {
      return t[c].amn = p, t[c].bmx = q, lz[c] += lv, void();
    }
  }
  down(c, l, r);
  if (y <= mid) upd(c << 1, l, mid, x, y, p, q, lv);
  else if (x > mid) upd(c << 1 | 1, mid + 1, r, x, y, p, q, lv);
  else upd(c << 1, l, mid, x, mid, p, q, lv), upd(c << 1 | 1, mid + 1, r, mid + 1, y, p, q, lv);
  t[c] = t[c << 1] + t[c << 1 | 1];
}

void print(int c, int l, int r) {
  if (l == r) return res.emplace_back(lz[c]), void();
  down(c, l, r);
  print(c << 1, l, mid), print(c << 1 | 1, mid + 1, r);
}

struct ST_mx {
  int t[maxn << 2];
  
  void build(int n, int w) {
    fill(t + 1, t + (n << 2) + 1, w);
  }
  
  void upd(int c, int l, int r, int x, int y, int v) {
    if (l == x && r == y) return chkmx(t[c], v), void();
    if (y <= mid) upd(c << 1, l, mid, x, y, v);
    else if (x > mid) upd(c << 1 | 1, mid + 1, r, x, y, v);
    else upd(c << 1, l, mid, x, mid, v), upd(c << 1 | 1, mid + 1, r, mid + 1, y, v);
  }
  
  void solve(int c, int l, int r, int *a) {
    if (l == r) return a[l] = t[c], void();
    chkmx(t[c << 1], t[c]), chkmx(t[c << 1 | 1], t[c]);
    solve(c << 1, l, mid, a), solve(c << 1 | 1, mid + 1, r, a);
  }
} tlmx;

struct ST_mn {
  int t[maxn << 2];
  
  void build(int n, int w) {
    fill(t + 1, t + (n << 2) + 1, w);
  }
  
  void upd(int c, int l, int r, int x, int y, int v) {
    if (l == x && r == y) return chkmn(t[c], v), void();
    if (y <= mid) upd(c << 1, l, mid, x, y, v);
    else if (x > mid) upd(c << 1 | 1, mid + 1, r, x, y, v);
    else upd(c << 1, l, mid, x, mid, v), upd(c << 1 | 1, mid + 1, r, mid + 1, y, v);
  }
  
  void solve(int c, int l, int r, int *a) {
    if (l == r) return a[l] = t[c], void();
    chkmn(t[c << 1], t[c]), chkmn(t[c << 1 | 1], t[c]);
    solve(c << 1, l, mid, a), solve(c << 1 | 1, mid + 1, r, a);
  }
} trmn;

#undef mid

void solve(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  vector<tuple<int, int, int, int>> vec;
  rep (i, l, r) {
    rep (j, 0, SZ(av[i]) - 2) {
      vec.emplace_back(av[i][j].se, av[i][j].fi, av[i][j + 1].fi - 1, i);
    }
  }
  sort(ALL(vec), greater<>());
  vector<int> delt;
  delt.reserve(SZ(vec) * 2);
  for (auto [val, l, r, pos] : vec) delt.emplace_back(l), delt.emplace_back(r + 1);
  sort(ALL(delt)), delt.erase(unique(ALL(delt)), delt.end()), tot = SZ(delt);
  for (auto &[val, l, r, pos] : vec) l = lower_bound(ALL(delt), l) - delt.begin();
  for (auto &[val, l, r, pos] : vec) r = lower_bound(ALL(delt), r + 1) - delt.begin() - 1;
  build(1, 0, tot - 2, l - 1, r + 1);
  for (int i = 0, j; i < SZ(vec); i = j + 1) {
    j = i;
    while (j + 1 < SZ(vec) && get<0>(vec[j + 1]) == get<0>(vec[j])) j++;
    vector<int> nd;
    nd.reserve((j - i + 1) * 2);
    rep (w, i, j) {
      auto [val, l, r, id] = vec[w];
      nd.emplace_back(l), nd.emplace_back(r + 1);
    }
    sort(ALL(nd)), nd.erase(unique(ALL(nd)), nd.end());
    tlmx.build(SZ(nd), l - 1), trmn.build(SZ(nd), r + 1);
    rep (w, i, j) {
      auto [val, l, r, id] = vec[w];
      l = lower_bound(ALL(nd), l) - nd.begin();
      r = lower_bound(ALL(nd), r + 1) - nd.begin() - 1;
      if (id <= mid) {
        tlmx.upd(1, 0, SZ(nd) - 1, l, r, id);
      } else {
        trmn.upd(1, 0, SZ(nd) - 1, l, r, id);
      }
    }
    tlmx.solve(1, 0, SZ(nd) - 1, lmx);
    trmn.solve(1, 0, SZ(nd) - 1, rmn);
    rep (w, 0, SZ(nd) - 2) {
      int l = nd[w], r = nd[w + 1] - 1;
      upd(1, 0, tot - 2, l, r, lmx[w], rmn[w], 1);
    }
  }
  res.clear(), print(1, 0, tot - 2);
  rep (i, 0, tot - 2) {
    int l = delt[i], r = delt[i + 1] - 1;
    c[l] += res[i], c[r + 1] -= res[i];
  }
  solve(l, mid), solve(mid + 1, r);
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m;
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, n) av[i].emplace_back(0, a[i]);
  rep (i, 1, m) {
    int x, v;
    cin >> x >> v;
    av[x].emplace_back(i, v);
  }
  rep (i, 1, n) av[i].emplace_back(m + 1, 0);
  solve(1, n);
  rep (i, 1, m) c[i] += c[i - 1];
  rep (i, 0, m) cout << c[i] << '\n';
}