假设我们有一个由 $$$n$$$ 不同数字 $$$a_1, a_2, \dots, a_n$$$ 组成的数组。让我们在 $$$n$$$ 顶点上构建一个图,如下所示:对于每对顶点 $$$i < j$$$,让我们用一条边连接 $$$i$$$ 和 $$$j$$$,如果 $$$a_i < a_j$$$。让我们将数组的权重定义为该图中连接的组件的数量。例如,数组$$$[1, 4, 2]$$$的权重为$$$1$$$,数组$$$[5, 4, 3]$$$的权重为$$$3$$$。
您必须执行以下形式的 $$$q$$$ 查询 - 更改数组某个位置的值。每次操作后,输出数组的权重。更新不是独立的(更改会保留到未来)。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^5$$$) - 数组的大小和查询的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 初始数组。
接下来的 $$$q$$$ 行包含两个整数 $$$pos$$$ 和 $$$x$$$ ($$$1 \le pos \le n$$$, $$$1 \le x \le 10^6, x \ne a_{pos}$$$)。这意味着你必须使$$$a_{pos}=x$$$。
保证在每个时刻,数组的所有元素都是不同的。
输出
每次查询后,输出数组的权重。
示例
输入 #1
5 3 50 40 30 20 10 1 25 3 45 1 48
输出 #1
3 3 4
注意
第一个查询数组看起来像 $$$[25, 40, 30, 20, 10]$$$ 后,权重等于 $$$3$$$。
第二个查询数组看起来像 $$$[25, 40, 45, 20, 10]$$$ 后,权重仍然等于 $$$3$$$。
第三个查询数组看起来像$$$[48, 40, 45, 20, 10]$$$后,权重等于$$$4$$$。