#include <bits/stdc++.h>
inline int min(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ first;
}
inline int max(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ second;
}
inline long long min(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ first;
}
inline long long max(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ second;
}
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace escape__from__random__aetuhoetnuhshe {
using namespace std::chrono;
mt19937 rng(duration_cast<milliseconds>(system_clock::now().time_since_epoch())
                .count());
uniform_real_distribution<> prob_dist(0.0, 1.0);
};  // namespace escape__from__random__aetuhoetnuhshe
namespace typedefs {}
namespace numbers_operation {
template <class T>
inline T floor_mod(T a, const T &b) {
  a %= b;
  if (a < 0) a += b;
  return a;
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
using namespace escape__from__random__aetuhoetnuhshe;
const long long N = (1 << 20);
long long T[2 * N + 1];
long long C[2 * N + 1];
long long D[2 * N + 1];
bool disabled[2 * N + 1];
long long get_value(long long i) {
  if (disabled[i]) return 1e9;
  return T[i] + D[i];
}
long long get_count(long long i) {
  if (disabled[i]) return 0;
  return C[i];
}
void push(long long i, long long tl, long long tr) {
  T[i] += D[i];
  if (tl + 1 != tr) {
    D[i * 2 + 1] += D[i];
    D[i * 2 + 2] += D[i];
  }
  D[i] = 0;
}
void update(long long i) {
  T[i] = min(get_value(i * 2 + 1), get_value(i * 2 + 2));
  C[i] = 0;
  if (T[i] == get_value(i * 2 + 1)) C[i] += get_count(i * 2 + 1);
  if (T[i] == get_value(i * 2 + 2)) C[i] += get_count(i * 2 + 2);
}
void inc(long long i, long long tl, long long tr, long long ql, long long qr,
         long long d) {
  if (qr <= tl || tr <= ql) return;
  push(i, tl, tr);
  if (ql <= tl && tr <= qr) {
    D[i] += d;
  } else {
    long long m = (tl + tr) / 2;
    inc(i * 2 + 1, tl, m, ql, qr, d);
    inc(i * 2 + 2, m, tr, ql, qr, d);
    update(i);
  }
}
void invoke(long long i, long long tl, long long tr, long long j, bool d) {
  push(i, tl, tr);
  if (tl + 1 == tr) {
    disabled[i] = d;
  } else {
    long long m = (tl + tr) / 2;
    if (j < m)
      invoke(i * 2 + 1, tl, m, j, d);
    else
      invoke(i * 2 + 2, m, tr, j, d);
    update(i);
  }
}
vector<long long> v;
void en(long long i, long long d) {
  if (i == ((long long)v.size()) - 1) return;
  long long a = v[i], b = v[i + 1];
  if (a > b) swap(a, b);
  inc(0, 0, N, a + 1, b + 1, d);
}
signed main(signed argc, char *argv[]) {
  for (long long i = 0; i < 2 * N; i++) {
    C[i] = 1;
  }
  for (long long i = N - 1; i < 2 * N; i++) disabled[i] = 1;
  for (long long i = N - 2; ~i; i--) {
    update(i);
  }
  long long n, q;
  cin, n, q;
  v.resize(n);
  cin, v;
  n += 2;
  v.insert(v.begin(), (long long)1e6 + 1);
  v.push_back(0);
  for (long long i = 0; i < n - 1; i++) {
    en(i, 1);
    invoke(0, 0, N, v[i], 0);
  }
  for (long long i = 0; i < q; i++) {
    long long pos, val;
    cin, pos, val;
    en(pos, -1);
    en(pos - 1, -1);
    invoke(0, 0, N, v[pos], 1);
    v[pos] = val;
    invoke(0, 0, N, v[pos], 0);
    en(pos, 1);
    en(pos - 1, 1);
    smart_io::precall_print();
    cout, C[0] - 1;
  }
}

### Prompt

Your task is to create a Cpp solution to the following problem:

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>
inline int min(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ first;
}
inline int max(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ second;
}
inline long long min(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ first;
}
inline long long max(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ second;
}
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace escape__from__random__aetuhoetnuhshe {
using namespace std::chrono;
mt19937 rng(duration_cast<milliseconds>(system_clock::now().time_since_epoch())
                .count());
uniform_real_distribution<> prob_dist(0.0, 1.0);
};  // namespace escape__from__random__aetuhoetnuhshe
namespace typedefs {}
namespace numbers_operation {
template <class T>
inline T floor_mod(T a, const T &b) {
  a %= b;
  if (a < 0) a += b;
  return a;
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
using namespace escape__from__random__aetuhoetnuhshe;
const long long N = (1 << 20);
long long T[2 * N + 1];
long long C[2 * N + 1];
long long D[2 * N + 1];
bool disabled[2 * N + 1];
long long get_value(long long i) {
  if (disabled[i]) return 1e9;
  return T[i] + D[i];
}
long long get_count(long long i) {
  if (disabled[i]) return 0;
  return C[i];
}
void push(long long i, long long tl, long long tr) {
  T[i] += D[i];
  if (tl + 1 != tr) {
    D[i * 2 + 1] += D[i];
    D[i * 2 + 2] += D[i];
  }
  D[i] = 0;
}
void update(long long i) {
  T[i] = min(get_value(i * 2 + 1), get_value(i * 2 + 2));
  C[i] = 0;
  if (T[i] == get_value(i * 2 + 1)) C[i] += get_count(i * 2 + 1);
  if (T[i] == get_value(i * 2 + 2)) C[i] += get_count(i * 2 + 2);
}
void inc(long long i, long long tl, long long tr, long long ql, long long qr,
         long long d) {
  if (qr <= tl || tr <= ql) return;
  push(i, tl, tr);
  if (ql <= tl && tr <= qr) {
    D[i] += d;
  } else {
    long long m = (tl + tr) / 2;
    inc(i * 2 + 1, tl, m, ql, qr, d);
    inc(i * 2 + 2, m, tr, ql, qr, d);
    update(i);
  }
}
void invoke(long long i, long long tl, long long tr, long long j, bool d) {
  push(i, tl, tr);
  if (tl + 1 == tr) {
    disabled[i] = d;
  } else {
    long long m = (tl + tr) / 2;
    if (j < m)
      invoke(i * 2 + 1, tl, m, j, d);
    else
      invoke(i * 2 + 2, m, tr, j, d);
    update(i);
  }
}
vector<long long> v;
void en(long long i, long long d) {
  if (i == ((long long)v.size()) - 1) return;
  long long a = v[i], b = v[i + 1];
  if (a > b) swap(a, b);
  inc(0, 0, N, a + 1, b + 1, d);
}
signed main(signed argc, char *argv[]) {
  for (long long i = 0; i < 2 * N; i++) {
    C[i] = 1;
  }
  for (long long i = N - 1; i < 2 * N; i++) disabled[i] = 1;
  for (long long i = N - 2; ~i; i--) {
    update(i);
  }
  long long n, q;
  cin, n, q;
  v.resize(n);
  cin, v;
  n += 2;
  v.insert(v.begin(), (long long)1e6 + 1);
  v.push_back(0);
  for (long long i = 0; i < n - 1; i++) {
    en(i, 1);
    invoke(0, 0, N, v[i], 0);
  }
  for (long long i = 0; i < q; i++) {
    long long pos, val;
    cin, pos, val;
    en(pos, -1);
    en(pos - 1, -1);
    invoke(0, 0, N, v[pos], 1);
    v[pos] = val;
    invoke(0, 0, N, v[pos], 0);
    en(pos, 1);
    en(pos - 1, 1);
    smart_io::precall_print();
    cout, C[0] - 1;
  }
}

```