#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long md = 11234549;
const long double PI = acosl(-1.0);
const long double E = 1e-15;
mt19937_64 rnd(time(0));
long long p1 = 227, p2 = 29 + rnd() % 100, md1 = MOD, md2 = MOD - rnd() % 1000;
long long n, m, k, T, ans, Z = 1e6 + 1, TT, a[1000005], kl[1000005];
long long binpow(long long h, long long r, long long md = MOD) {
  long long l = 1;
  while (r) {
    if (r & 1) l *= h, l %= md;
    h *= h;
    h %= md;
    r /= 2;
  }
  return l;
}
pair<pair<int, bool>, int> d[5000000];
int tt[5000000];
void push(int h) {
  if (tt[h]) {
    tt[h * 2] += tt[h];
    tt[h * 2 + 1] += tt[h];
    d[h * 2].first.first += tt[h];
    d[h * 2 + 1].first.first += tt[h];
    tt[h] = 0;
  }
}
void build(int h, int l, int r) {
  if (l == r) {
    d[h].second = 1;
    return;
  }
  int w = (l + r) / 2;
  build(h * 2, l, w);
  build(h * 2 + 1, w + 1, r);
  d[h].second = d[h * 2].second + d[h * 2 + 1].second;
}
void upd(int h, int l, int r, int x, int k) {
  if (l == r) {
    d[h].first.second = k;
    return;
  }
  push(h);
  int w = (l + r) / 2;
  if (x <= w)
    upd(h * 2, l, w, x, k);
  else
    upd(h * 2 + 1, w + 1, r, x, k);
  if (d[h * 2].first.second > d[h * 2 + 1].first.second)
    d[h] = d[h * 2];
  else if (d[h * 2].first.second < d[h * 2 + 1].first.second)
    d[h] = d[h * 2 + 1];
  else if (d[h * 2].first.first < d[h * 2 + 1].first.first)
    d[h] = d[h * 2];
  else if (d[h * 2].first.first > d[h * 2 + 1].first.first)
    d[h] = d[h * 2 + 1];
  else
    d[h] = make_pair(d[h * 2].first, d[h * 2].second + d[h * 2 + 1].second);
}
void update(int h, int l, int r, int x, int y, int k) {
  if (x > y) return;
  push(h);
  if (l == x && y == r) {
    d[h].first.first += k;
    tt[h] += k;
    return;
  }
  int w = (l + r) / 2;
  update(h * 2, l, w, x, min(y, w), k);
  update(h * 2 + 1, w + 1, r, max(x, w + 1), y, k);
  if (d[h * 2].first.second > d[h * 2 + 1].first.second)
    d[h] = d[h * 2];
  else if (d[h * 2].first.second < d[h * 2 + 1].first.second)
    d[h] = d[h * 2 + 1];
  else if (d[h * 2].first.first < d[h * 2 + 1].first.first)
    d[h] = d[h * 2];
  else if (d[h * 2].first.first > d[h * 2 + 1].first.first)
    d[h] = d[h * 2 + 1];
  else
    d[h] = make_pair(d[h * 2].first, d[h * 2].second + d[h * 2 + 1].second);
}
pair<pair<int, bool>, int> get(int h, int l, int r, int x, int y) {
  if (x > y) return make_pair(make_pair(0, 0), 0);
  if (l == x && y == r) return d[h];
  push(h);
  int w = (l + r) / 2;
  auto o1 = get(h * 2, l, w, x, min(y, w)),
       o2 = get(h * 2 + 1, w + 1, r, max(x, w + 1), y);
  if (o1.first.second > o2.first.second)
    return o1;
  else if (o1.first.second < o2.first.second)
    return o2;
  else if (o1.first.first < o2.first.first)
    return o1;
  else if (o1.first.first > o2.first.first)
    return o2;
  else
    return make_pair(o1.first, o1.second + o2.second);
}
void solve() {
  long long q;
  cin >> n >> q;
  a[0] = 1e6 + 1;
  build(1, 0, Z);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    kl[a[i]]++;
    upd(1, 0, Z, a[i], 1);
    update(1, 0, Z, min(a[i], a[i - 1]), max(a[i], a[i - 1]) - 1, 1);
  }
  vector<long long> an;
  update(1, 0, Z, 0, a[n] - 1, 1);
  for (int i = 1; i <= q; i++) {
    long long x, y;
    cin >> x >> y;
    update(1, 0, Z, min(a[x], a[x - 1]), max(a[x], a[x - 1]) - 1, -1);
    update(1, 0, Z, min(a[x], a[x + 1]), max(a[x], a[x + 1]) - 1, -1);
    kl[a[x]]--;
    if (kl[a[x]] == 0) upd(1, 0, Z, a[x], 0);
    a[x] = y;
    kl[a[x]]++;
    if (kl[a[x]] == 1) upd(1, 0, Z, a[x], 1);
    update(1, 0, Z, min(a[x], a[x - 1]), max(a[x], a[x - 1]) - 1, 1);
    update(1, 0, Z, min(a[x], a[x + 1]), max(a[x], a[x + 1]) - 1, 1);
    pair<pair<int, bool>, int> o = get(1, 0, Z, 0, Z);
    if (o.first.second != 1 || o.first.first != 1) {
      cout << i << " " << o.first.first << " " << o.first.second << " "
           << o.second << "\n";
      exit(0);
    } else
      an.push_back(o.second);
  }
  for (int i = 0; i < an.size(); i++) cout << an[i] << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
