#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10, SQ1 = 1500, SQ2 = (maxn / SQ1) + 3, inf = 1e8;
template <typename A, typename B>
ostream& operator<<(ostream& out, pair<A, B> p) {
  out << "{ " << p.first << ", " << p.second << " }";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> v) {
  out << "[ ";
  for (int i = 0; i < int((v).size()); i++) {
    out << v[i];
    if (i != int((v).size()) - 1) out << " ,";
  }
  out << " ]";
  return out;
}
int a[SQ2][SQ1 + 10], mn[SQ2][SQ1 + 10], mx[SQ2][SQ1 + 10], MN[SQ2 + 10],
    MX[SQ2 + 10];
vector<int> mnv[SQ2], mxv[SQ2];
int BMN[SQ2], BMX[SQ2], RMN[SQ2], LMX[SQ2];
void build(int i) {
  BMN[i] = BMX[i] = inf + 1000;
  mn[i][0] = a[i][0];
  for (int j = 1; j < SQ1; j++) mn[i][j] = min(mn[i][j - 1], a[i][j]);
  mx[i][SQ1] = -inf;
  for (int j = SQ1 - 1; j >= 0; j--) mx[i][j] = max(mx[i][j + 1], a[i][j]);
  mnv[i].clear();
  mxv[i].clear();
  for (int j = 0; j < SQ1; j++) {
    if (mn[i][j] >= mx[i][j + 1])
      mnv[i].push_back(mn[i][j]), mxv[i].push_back(mx[i][j + 1]);
  }
  reverse(mnv[i].begin(), mnv[i].end());
  reverse(mxv[i].begin(), mxv[i].end());
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < SQ2; i++)
    for (int j = 0; j < SQ1 + 10; j++) a[i][j] = -inf;
  for (int i = 0; i < n; i++) {
    cin >> a[i / SQ1][i % SQ1];
  }
  int N = (n - 1) / SQ1;
  for (int i = 0; i <= N; i++) {
    build(i);
  }
  while (q--) {
    int pos, x;
    cin >> pos >> x;
    --pos;
    a[pos / SQ1][pos % SQ1] = x;
    build(pos / SQ1);
    int ans = 0;
    for (int i = 0; i <= N; i++)
      MN[i] = min((i == 0 ? inf : MN[i - 1]), mn[i][SQ1 - 1]);
    MX[N + 1] = -inf + 1;
    for (int i = N; i >= 0; i--) MX[i] = max(MX[i + 1], mx[i][0]);
    int _MN = inf, _MX = MX[1];
    for (int i = 0; i <= N; i++) {
      if (_MN >= _MX) {
        if (_MN != BMN[i])
          RMN[i] =
              upper_bound(mxv[i].begin(), mxv[i].end(), _MN) - mxv[i].begin();
        if (_MX != BMX[i])
          LMX[i] =
              lower_bound(mnv[i].begin(), mnv[i].end(), _MX) - mnv[i].begin();
        BMN[i] = _MN, BMX[i] = _MX;
        ans += max(int(0), RMN[i] - LMX[i]);
      }
      _MN = MN[i], _MX = MX[i + 2];
    }
    cout << ans << "\n";
  }
  return 0;
}
