#include <bits/stdc++.h>
using namespace std;
const long long maxn = 5e5 + 10;
const long long maxa = 1e6 + 10;
const long long INF = 1e9 + 1;
long long n, q, p[maxn], pp[maxn], a[maxn], f[maxa], ind[maxa], minn[4 * maxa],
    minn2[4 * maxa], cntmin[4 * maxa], la1[4 * maxa], la2[4 * maxa];
void build(long long l = 1, long long r = 1000000, long long node = 1) {
  if (l == r) {
    minn[node] = INF;
    minn2[node] = f[l];
    cntmin[node] = 1;
    return;
  }
  long long mid = (r + l) / 2;
  build(l, mid, 2 * node);
  build(mid + 1, r, (2 * node) + 1);
  minn[node] = min(minn[2 * node], minn[(2 * node) + 1]);
  cntmin[node] = 0;
  if (minn[2 * node] == minn[node]) cntmin[node] += cntmin[2 * node];
  if (minn[(2 * node) + 1] == minn[node])
    cntmin[node] += cntmin[(2 * node) + 1];
  minn2[node] = min(minn2[2 * node], minn2[(2 * node) + 1]);
}
void shift1(long long l, long long r, long long node) {
  minn[node] += la1[node];
  if (l == r) {
    la1[node] = 0;
    return;
  }
  la1[2 * node] += la1[node];
  la1[(2 * node) + 1] += la1[node];
  la1[node] = 0;
}
void shift2(long long l, long long r, long long node) {
  minn2[node] += la2[node];
  if (l == r) {
    la2[node] = 0;
    return;
  }
  la2[2 * node] += la2[node];
  la2[(2 * node) + 1] += la2[node];
  la2[node] = 0;
}
void up1(long long x, long long y, long long va, long long l = 1,
         long long r = 1000000, long long node = 1) {
  shift1(l, r, node);
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    minn[node] = va;
    return;
  }
  long long mid = (r + l) / 2;
  up1(x, y, va, l, mid, 2 * node);
  up1(x, y, va, mid + 1, r, (2 * node) + 1);
  minn[node] = min(minn[2 * node], minn[(2 * node) + 1]);
  cntmin[node] = 0;
  if (minn[2 * node] == minn[node]) cntmin[node] += cntmin[2 * node];
  if (minn[(2 * node) + 1] == minn[node])
    cntmin[node] += cntmin[(2 * node) + 1];
}
long long get2(long long x, long long y, long long l = 1, long long r = 1000000,
               long long node = 1) {
  shift2(l, r, node);
  if (l > y || r < x) return 0;
  if (l >= x && r <= y) return minn2[node];
  long long mid = (r + l) / 2;
  return get2(x, y, l, mid, 2 * node) + get2(x, y, mid + 1, r, (2 * node) + 1);
}
long long get1(long long x, long long y, long long l = 1, long long r = 1000000,
               long long node = 1) {
  shift1(l, r, node);
  if (l > y || r < x) return 0;
  if (l >= x && r <= y) return minn[node];
  long long mid = (r + l) / 2;
  return get1(x, y, l, mid, 2 * node) + get1(x, y, mid + 1, r, (2 * node) + 1);
}
void add1(long long x, long long y, long long va, long long l = 1,
          long long r = 1000000, long long node = 1) {
  if (x > y) return;
  shift1(l, r, node);
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    la1[node] += va;
    shift1(l, r, node);
    return;
  }
  long long mid = (r + l) / 2;
  add1(x, y, va, l, mid, 2 * node);
  add1(x, y, va, mid + 1, r, (2 * node) + 1);
  minn[node] = min(minn[2 * node], minn[(2 * node) + 1]);
  cntmin[node] = 0;
  if (minn[2 * node] == minn[node]) cntmin[node] += cntmin[2 * node];
  if (minn[(2 * node) + 1] == minn[node])
    cntmin[node] += cntmin[(2 * node) + 1];
}
void add2(long long x, long long y, long long va, long long l = 1,
          long long r = 1000000, long long node = 1) {
  if (x > y) return;
  shift2(l, r, node);
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    la2[node] += va;
    shift2(l, r, node);
    return;
  }
  long long mid = (r + l) / 2;
  add2(x, y, va, l, mid, 2 * node);
  add2(x, y, va, mid + 1, r, (2 * node) + 1);
  minn2[node] = min(minn2[2 * node], minn2[(2 * node) + 1]);
}
int main() {
  std::ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    pp[i] = p[i];
    ind[p[i]] = i;
  }
  sort(pp + 1, pp + n + 1);
  long long now = 1;
  a[0] = INF;
  for (int i = n; i > 0; i--) {
    long long idx = ind[pp[i]];
    a[idx] = pp[i];
    if (a[idx - 1] == 0)
      now++;
    else
      now--;
    if (a[idx + 1] == 0)
      now++;
    else
      now--;
    f[pp[i]] = now;
  }
  long long x = 1;
  for (int i = (1e6); i > 0; i--) {
    if (f[i] == 0)
      f[i] = x;
    else
      x = f[i];
  }
  build();
  for (int i = 1; i <= n; i++) up1(p[i], p[i], f[p[i]]);
  while (q--) {
    long long pos, van;
    cin >> pos >> van;
    long long va = a[pos];
    long long fvan = get2(van, van);
    up1(va, va, INF);
    up1(van, van, fvan);
    long long i = pos;
    if (van > va) {
      add1(max(a[i], a[i - 1]) + 1, van, 1);
      add1(a[i] + 1, min(a[i - 1], van), -1);
      add1(max(a[i], a[i + 1]) + 1, van, 1);
      add1(a[i] + 1, min(a[i + 1], van), -1);
      add2(max(a[i], a[i - 1]) + 1, van, 1);
      add2(a[i] + 1, min(a[i - 1], van), -1);
      add2(max(a[i], a[i + 1]) + 1, van, 1);
      add2(a[i] + 1, min(a[i + 1], van), -1);
    } else if (van < va) {
      add1(max(van + 1, a[i - 1] + 1), a[i], -1);
      add1(max(van + 1, a[i + 1] + 1), a[i], -1);
      add1(van + 1, min(a[i], a[i - 1]), 1);
      add1(van + 1, min(a[i], a[i + 1]), 1);
      add2(max(van + 1, a[i - 1] + 1), a[i], -1);
      add2(max(van + 1, a[i + 1] + 1), a[i], -1);
      add2(van + 1, min(a[i], a[i - 1]), 1);
      add2(van + 1, min(a[i], a[i + 1]), 1);
    }
    a[pos] = van;
    cout << cntmin[1] << "\n";
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

Suppose that we have an array of n distinct numbers a_1, a_2, ..., a_n. Let's build a graph on n vertices as follows: for every pair of vertices i < j let's connect i and j with an edge, if a_i < a_j. Let's define weight of the array to be the number of connected components in this graph. For example, weight of array [1, 4, 2] is 1, weight of array [5, 4, 3] is 3.

You have to perform q queries of the following form — change the value at some position of the array. After each operation, output the weight of the array. Updates are not independent (the change stays for the future).

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 5 ⋅ 10^5) — the size of the array and the number of queries.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6) — the initial array.

Each of the next q lines contains two integers pos and x (1 ≤ pos ≤ n, 1 ≤ x ≤ 10^6, x ≠ a_{pos}). It means that you have to make a_{pos}=x.

It's guaranteed that at every moment of time, all elements of the array are different.

Output

After each query, output the weight of the array.

Example

Input


5 3
50 40 30 20 10
1 25
3 45
1 48


Output


3
3
4

Note

After the first query array looks like [25, 40, 30, 20, 10], the weight is equal to 3.

After the second query array looks like [25, 40, 45, 20, 10], the weight is still equal to 3.

After the third query array looks like [48, 40, 45, 20, 10], the weight is equal to 4.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 5e5 + 10;
const long long maxa = 1e6 + 10;
const long long INF = 1e9 + 1;
long long n, q, p[maxn], pp[maxn], a[maxn], f[maxa], ind[maxa], minn[4 * maxa],
    minn2[4 * maxa], cntmin[4 * maxa], la1[4 * maxa], la2[4 * maxa];
void build(long long l = 1, long long r = 1000000, long long node = 1) {
  if (l == r) {
    minn[node] = INF;
    minn2[node] = f[l];
    cntmin[node] = 1;
    return;
  }
  long long mid = (r + l) / 2;
  build(l, mid, 2 * node);
  build(mid + 1, r, (2 * node) + 1);
  minn[node] = min(minn[2 * node], minn[(2 * node) + 1]);
  cntmin[node] = 0;
  if (minn[2 * node] == minn[node]) cntmin[node] += cntmin[2 * node];
  if (minn[(2 * node) + 1] == minn[node])
    cntmin[node] += cntmin[(2 * node) + 1];
  minn2[node] = min(minn2[2 * node], minn2[(2 * node) + 1]);
}
void shift1(long long l, long long r, long long node) {
  minn[node] += la1[node];
  if (l == r) {
    la1[node] = 0;
    return;
  }
  la1[2 * node] += la1[node];
  la1[(2 * node) + 1] += la1[node];
  la1[node] = 0;
}
void shift2(long long l, long long r, long long node) {
  minn2[node] += la2[node];
  if (l == r) {
    la2[node] = 0;
    return;
  }
  la2[2 * node] += la2[node];
  la2[(2 * node) + 1] += la2[node];
  la2[node] = 0;
}
void up1(long long x, long long y, long long va, long long l = 1,
         long long r = 1000000, long long node = 1) {
  shift1(l, r, node);
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    minn[node] = va;
    return;
  }
  long long mid = (r + l) / 2;
  up1(x, y, va, l, mid, 2 * node);
  up1(x, y, va, mid + 1, r, (2 * node) + 1);
  minn[node] = min(minn[2 * node], minn[(2 * node) + 1]);
  cntmin[node] = 0;
  if (minn[2 * node] == minn[node]) cntmin[node] += cntmin[2 * node];
  if (minn[(2 * node) + 1] == minn[node])
    cntmin[node] += cntmin[(2 * node) + 1];
}
long long get2(long long x, long long y, long long l = 1, long long r = 1000000,
               long long node = 1) {
  shift2(l, r, node);
  if (l > y || r < x) return 0;
  if (l >= x && r <= y) return minn2[node];
  long long mid = (r + l) / 2;
  return get2(x, y, l, mid, 2 * node) + get2(x, y, mid + 1, r, (2 * node) + 1);
}
long long get1(long long x, long long y, long long l = 1, long long r = 1000000,
               long long node = 1) {
  shift1(l, r, node);
  if (l > y || r < x) return 0;
  if (l >= x && r <= y) return minn[node];
  long long mid = (r + l) / 2;
  return get1(x, y, l, mid, 2 * node) + get1(x, y, mid + 1, r, (2 * node) + 1);
}
void add1(long long x, long long y, long long va, long long l = 1,
          long long r = 1000000, long long node = 1) {
  if (x > y) return;
  shift1(l, r, node);
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    la1[node] += va;
    shift1(l, r, node);
    return;
  }
  long long mid = (r + l) / 2;
  add1(x, y, va, l, mid, 2 * node);
  add1(x, y, va, mid + 1, r, (2 * node) + 1);
  minn[node] = min(minn[2 * node], minn[(2 * node) + 1]);
  cntmin[node] = 0;
  if (minn[2 * node] == minn[node]) cntmin[node] += cntmin[2 * node];
  if (minn[(2 * node) + 1] == minn[node])
    cntmin[node] += cntmin[(2 * node) + 1];
}
void add2(long long x, long long y, long long va, long long l = 1,
          long long r = 1000000, long long node = 1) {
  if (x > y) return;
  shift2(l, r, node);
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    la2[node] += va;
    shift2(l, r, node);
    return;
  }
  long long mid = (r + l) / 2;
  add2(x, y, va, l, mid, 2 * node);
  add2(x, y, va, mid + 1, r, (2 * node) + 1);
  minn2[node] = min(minn2[2 * node], minn2[(2 * node) + 1]);
}
int main() {
  std::ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    pp[i] = p[i];
    ind[p[i]] = i;
  }
  sort(pp + 1, pp + n + 1);
  long long now = 1;
  a[0] = INF;
  for (int i = n; i > 0; i--) {
    long long idx = ind[pp[i]];
    a[idx] = pp[i];
    if (a[idx - 1] == 0)
      now++;
    else
      now--;
    if (a[idx + 1] == 0)
      now++;
    else
      now--;
    f[pp[i]] = now;
  }
  long long x = 1;
  for (int i = (1e6); i > 0; i--) {
    if (f[i] == 0)
      f[i] = x;
    else
      x = f[i];
  }
  build();
  for (int i = 1; i <= n; i++) up1(p[i], p[i], f[p[i]]);
  while (q--) {
    long long pos, van;
    cin >> pos >> van;
    long long va = a[pos];
    long long fvan = get2(van, van);
    up1(va, va, INF);
    up1(van, van, fvan);
    long long i = pos;
    if (van > va) {
      add1(max(a[i], a[i - 1]) + 1, van, 1);
      add1(a[i] + 1, min(a[i - 1], van), -1);
      add1(max(a[i], a[i + 1]) + 1, van, 1);
      add1(a[i] + 1, min(a[i + 1], van), -1);
      add2(max(a[i], a[i - 1]) + 1, van, 1);
      add2(a[i] + 1, min(a[i - 1], van), -1);
      add2(max(a[i], a[i + 1]) + 1, van, 1);
      add2(a[i] + 1, min(a[i + 1], van), -1);
    } else if (van < va) {
      add1(max(van + 1, a[i - 1] + 1), a[i], -1);
      add1(max(van + 1, a[i + 1] + 1), a[i], -1);
      add1(van + 1, min(a[i], a[i - 1]), 1);
      add1(van + 1, min(a[i], a[i + 1]), 1);
      add2(max(van + 1, a[i - 1] + 1), a[i], -1);
      add2(max(van + 1, a[i + 1] + 1), a[i], -1);
      add2(van + 1, min(a[i], a[i - 1]), 1);
      add2(van + 1, min(a[i], a[i + 1]), 1);
    }
    a[pos] = van;
    cout << cntmin[1] << "\n";
  }
  return 0;
}

```