#include <bits/stdc++.h>
using namespace std;
mt19937 rng(static_cast<unsigned int>(
    chrono::steady_clock::now().time_since_epoch().count()));
template <typename num_t>
inline void add_mod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void unsafe_add_mod(num_t& a, const long long& b, const int& m) {
  a += b;
  if (a < 0)
    a += m;
  else if (a >= m)
    a -= m;
}
template <typename num_t>
inline bool update_max(num_t& a, const num_t& b) {
  return a < b ? a = b, true : false;
}
template <typename num_t>
inline bool update_min(num_t& a, const num_t& b) {
  return a > b ? a = b, true : false;
}
template <typename num_t>
num_t gcd(const num_t& lhs, const num_t& rhs) {
  return !lhs ? rhs : gcd(rhs % lhs, lhs);
}
template <typename num_t>
num_t lcm(const num_t& lhs, const num_t& rhs) {
  return lhs / ::gcd(lhs, rhs) * rhs;
}
template <typename num_t>
num_t pw(num_t n, num_t k, const num_t& mod) {
  if (k == -1) k = mod - 2;
  num_t res = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) res = 1ll * res * n % mod;
    n = 1ll * n * n % mod;
  }
  return res % mod;
}
const int inf = 1e9 + 7;
const int mod = 998244353;
const long long ll_inf = (long long)inf * inf * 9 + 7;
const int maxn = 200000 + 7;
template <typename num_t>
class SegmentTree {
 public:
  void init(int l, int r) {
    tree.resize((r - l + 1) << 1);
    node_index = 0;
    build_tree(tree[node_index++], l, r);
  }
  void update(int left_index, int right_index, const num_t& val) {
    update_(tree[0], left_index, right_index, val);
  }
  num_t get() { return tree[0].count; }
  num_t get(int left_index, int right_index) {
    if (right_index < left_index) return 0;
    return get(tree[0], left_index, right_index);
  }

 private:
  struct node {
    static const num_t nil = 0;
    node *left_child, *right_child;
    int left_index, right_index;
    num_t value = 0;
    num_t lazy = 0;
    num_t count = 0;
    inline void push_down(num_t updated_value) {
      if (abs(updated_value) >= inf) {
        if (updated_value > 0)
          count = 1;
        else
          count = 0;
      } else {
        value += updated_value;
        lazy += updated_value;
      }
    }
    inline void merge_node() {
      const node &lhs = *left_child, &rhs = *right_child;
      if (lhs.value < rhs.value) {
        value = lhs.value;
        count = lhs.count;
      } else if (lhs.value > rhs.value) {
        value = rhs.value;
        count = rhs.count;
      } else {
        value = lhs.value;
        count = lhs.count + rhs.count;
      }
    }
    inline void lazy_update() {
      if (lazy) {
        if (left_child != nullptr) left_child->push_down(lazy);
        if (right_child != nullptr) right_child->push_down(lazy);
        lazy = 0;
      }
    }
    inline void init_value(num_t v = 0) {
      value = 0;
      count = 1;
    }
    inline void init(int left, int right, node* left_child_,
                     node* right_child_) {
      left_index = left;
      right_index = right;
      left_child = left_child_;
      right_child = right_child_;
    }
    int size() const { return right_index - left_index + 1; }
  };
  vector<node> tree;
  int node_index = 0;
  void build_tree(node& root, int left, int right) {
    if (left == right) {
      root.init(left, right, nullptr, nullptr);
      root.init_value(0);
      return;
    }
    int mid = (left + right) >> 1, lhs = node_index++, rhs = node_index++;
    build_tree(tree[lhs], left, mid);
    build_tree(tree[rhs], mid + 1, right);
    root.init(left, right, &tree[lhs], &tree[rhs]);
    root.init_value(0);
    root.merge_node();
  }
  void update_(node& root, int u, int v, const num_t& value) {
    if (u > root.right_index || v < root.left_index) return;
    if (u <= root.left_index && root.right_index <= v) {
      root.push_down(value);
    } else {
      root.lazy_update();
      update_(*root.left_child, u, v, value);
      update_(*root.right_child, u, v, value);
      root.merge_node();
    }
  }
  num_t get(node& root, int u, int v) {
    if (u <= root.left_index && root.right_index <= v) return root.value;
    if (u > root.right_index || v < root.left_index) return node::nil;
    root.lazy_update();
    auto lhs = get(*root.left_child, u, v);
    auto rhs = get(*root.right_child, u, v);
    return max(lhs, rhs);
  }
};
SegmentTree<int> segment_tree;
const int maxh = 1000000;
void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n + 2, 0);
  a[0] = maxh;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  segment_tree.init(1, maxh);
  for (int i = 1; i <= n + 1; ++i)
    if (a[i - 1] > a[i]) {
      segment_tree.update(a[i] + 1, a[i - 1], 1);
    }
  set<int> h_values(a.begin() + 1, a.end());
  for (int h = 1; h <= maxh; ++h)
    if (!h_values.count(h)) segment_tree.update(h, h, -inf);
  auto update = [&](int pos, int diff) {
    if (a[pos - 1] > a[pos]) {
      segment_tree.update(a[pos] + 1, a[pos - 1], diff);
    }
    if (a[pos] > a[pos + 1]) {
      segment_tree.update(a[pos + 1] + 1, a[pos], diff);
    }
    segment_tree.update(a[pos], a[pos], diff * inf);
  };
  while (q-- > 0) {
    int pos, value;
    cin >> pos >> value;
    update(pos, -1);
    a[pos] = value;
    update(pos, 1);
    cout << segment_tree.get() << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}

### Prompt

In CPP, your task is to solve 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>
using namespace std;
mt19937 rng(static_cast<unsigned int>(
    chrono::steady_clock::now().time_since_epoch().count()));
template <typename num_t>
inline void add_mod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void unsafe_add_mod(num_t& a, const long long& b, const int& m) {
  a += b;
  if (a < 0)
    a += m;
  else if (a >= m)
    a -= m;
}
template <typename num_t>
inline bool update_max(num_t& a, const num_t& b) {
  return a < b ? a = b, true : false;
}
template <typename num_t>
inline bool update_min(num_t& a, const num_t& b) {
  return a > b ? a = b, true : false;
}
template <typename num_t>
num_t gcd(const num_t& lhs, const num_t& rhs) {
  return !lhs ? rhs : gcd(rhs % lhs, lhs);
}
template <typename num_t>
num_t lcm(const num_t& lhs, const num_t& rhs) {
  return lhs / ::gcd(lhs, rhs) * rhs;
}
template <typename num_t>
num_t pw(num_t n, num_t k, const num_t& mod) {
  if (k == -1) k = mod - 2;
  num_t res = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) res = 1ll * res * n % mod;
    n = 1ll * n * n % mod;
  }
  return res % mod;
}
const int inf = 1e9 + 7;
const int mod = 998244353;
const long long ll_inf = (long long)inf * inf * 9 + 7;
const int maxn = 200000 + 7;
template <typename num_t>
class SegmentTree {
 public:
  void init(int l, int r) {
    tree.resize((r - l + 1) << 1);
    node_index = 0;
    build_tree(tree[node_index++], l, r);
  }
  void update(int left_index, int right_index, const num_t& val) {
    update_(tree[0], left_index, right_index, val);
  }
  num_t get() { return tree[0].count; }
  num_t get(int left_index, int right_index) {
    if (right_index < left_index) return 0;
    return get(tree[0], left_index, right_index);
  }

 private:
  struct node {
    static const num_t nil = 0;
    node *left_child, *right_child;
    int left_index, right_index;
    num_t value = 0;
    num_t lazy = 0;
    num_t count = 0;
    inline void push_down(num_t updated_value) {
      if (abs(updated_value) >= inf) {
        if (updated_value > 0)
          count = 1;
        else
          count = 0;
      } else {
        value += updated_value;
        lazy += updated_value;
      }
    }
    inline void merge_node() {
      const node &lhs = *left_child, &rhs = *right_child;
      if (lhs.value < rhs.value) {
        value = lhs.value;
        count = lhs.count;
      } else if (lhs.value > rhs.value) {
        value = rhs.value;
        count = rhs.count;
      } else {
        value = lhs.value;
        count = lhs.count + rhs.count;
      }
    }
    inline void lazy_update() {
      if (lazy) {
        if (left_child != nullptr) left_child->push_down(lazy);
        if (right_child != nullptr) right_child->push_down(lazy);
        lazy = 0;
      }
    }
    inline void init_value(num_t v = 0) {
      value = 0;
      count = 1;
    }
    inline void init(int left, int right, node* left_child_,
                     node* right_child_) {
      left_index = left;
      right_index = right;
      left_child = left_child_;
      right_child = right_child_;
    }
    int size() const { return right_index - left_index + 1; }
  };
  vector<node> tree;
  int node_index = 0;
  void build_tree(node& root, int left, int right) {
    if (left == right) {
      root.init(left, right, nullptr, nullptr);
      root.init_value(0);
      return;
    }
    int mid = (left + right) >> 1, lhs = node_index++, rhs = node_index++;
    build_tree(tree[lhs], left, mid);
    build_tree(tree[rhs], mid + 1, right);
    root.init(left, right, &tree[lhs], &tree[rhs]);
    root.init_value(0);
    root.merge_node();
  }
  void update_(node& root, int u, int v, const num_t& value) {
    if (u > root.right_index || v < root.left_index) return;
    if (u <= root.left_index && root.right_index <= v) {
      root.push_down(value);
    } else {
      root.lazy_update();
      update_(*root.left_child, u, v, value);
      update_(*root.right_child, u, v, value);
      root.merge_node();
    }
  }
  num_t get(node& root, int u, int v) {
    if (u <= root.left_index && root.right_index <= v) return root.value;
    if (u > root.right_index || v < root.left_index) return node::nil;
    root.lazy_update();
    auto lhs = get(*root.left_child, u, v);
    auto rhs = get(*root.right_child, u, v);
    return max(lhs, rhs);
  }
};
SegmentTree<int> segment_tree;
const int maxh = 1000000;
void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n + 2, 0);
  a[0] = maxh;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  segment_tree.init(1, maxh);
  for (int i = 1; i <= n + 1; ++i)
    if (a[i - 1] > a[i]) {
      segment_tree.update(a[i] + 1, a[i - 1], 1);
    }
  set<int> h_values(a.begin() + 1, a.end());
  for (int h = 1; h <= maxh; ++h)
    if (!h_values.count(h)) segment_tree.update(h, h, -inf);
  auto update = [&](int pos, int diff) {
    if (a[pos - 1] > a[pos]) {
      segment_tree.update(a[pos] + 1, a[pos - 1], diff);
    }
    if (a[pos] > a[pos + 1]) {
      segment_tree.update(a[pos + 1] + 1, a[pos], diff);
    }
    segment_tree.update(a[pos], a[pos], diff * inf);
  };
  while (q-- > 0) {
    int pos, value;
    cin >> pos >> value;
    update(pos, -1);
    a[pos] = value;
    update(pos, 1);
    cout << segment_tree.get() << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}

```