沿直线道路立有 $N$ 盏路灯。第 $i$ 盏路灯的初始高度为 $A_i$ ($1 \le i \le N$)。 计划利用这些路灯架设电线。 要在第 $i$ 盏路灯和第 $j$ ($j > i$) 盏路灯之间架设电线，必须同时满足以下两个条件： $A_i = A_j$（两盏路灯的高度相等。） 对于所有 $i < k < j$，满足 $A_k < A_i$。（两盏路灯之间的所有路灯高度均低于这两盏路灯。）

根据管理人员的判断，部分路灯的高度会进行调整，高度调整后，可架设电线的情况也会随之改变。 共有 $Q$ 次高度调整操作，每次操作为“将第 $x$ 盏路灯的高度更改为 $h$”。每进行一次高度调整，都需要编写一个程序来计算调整后可以架设电线的路灯对数。

实现细节

你需要实现以下函数：

vector<long long int> count_cable(vector<int> A, vector< pair<int, int> > C)

• 该函数仅会被调用一次。
• 参数数组 $A$ 的大小为 $N$。数组 $A$ 的每个元素表示路灯的初始高度。即 $A[i] = A_{i+1}$ ($0 \le i \le N - 1$)。
• 参数 $C$ 是一个包含 $Q$ 个有序对 $(x, h)$ 的数组，每个有序对 $(x, h)$ 表示“将第 $x$ 盏路灯的高度更改为 $h$”的操作。
• 该函数应返回一个大小为 $Q+1$ 的整数数组，其中存储了初始状态下可架设的电线数量，以及每次高度调整后可架设的电线数量。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $2 \le N \le 100\,000$
• $1 \le Q \le 250\,000$
• 所有路灯的高度均为 $1$ 以上 $10^9$ 以下的整数。
• 在将第 $x$ 盏路灯高度更改为 $h$ 的操作中，保证 $1 \le x \le N$，且第 $x$ 盏路灯的高度确实会发生变化。即调整前第 $x$ 盏路灯的高度与 $h$ 不同。

子任务

1. (5分) $N \le 50$, $Q \le 100$
2. (8分) $N \le 10\,000$, $Q \le 25\,000$
3. (11分) 所有路灯的高度始终不超过 $10$。
4. (7分) 所有高度调整操作均会减小路灯高度。
5. (15分) 曾经增加过高度的路灯，之后高度不会减小；曾经减小过高度的路灯，之后高度不会增加。
6. (12分) $Q \le 8\,000$
7. (16分) 至少发生过一次高度变化的路灯总数不超过 $8\,000$ 个。
8. (21分) $N \le 40\,000$, $Q \le 100\,000$
9. (55分) 无附加限制。

说明

注意：每个子任务的得分为该子任务所有测试数据的得分最小值。

样例

考虑 $A = [4, 2, 2, 2, 4, 6]$, $C = [(4, 6), (6, 4)]$ 的情况。 $C = [(4, 6), (6, 4)]$ 的含义是：第一次高度调整将第 $4$ 盏路灯的高度改为 $6$，第二次高度调整将第 $6$ 盏路灯的高度改为 $4$。 评测程序将调用以下函数：

count_cable([4,2,2,2,4,6], [(4,6),(6,4)])

下图展示了初始状态下 $6$ 盏路灯可架设电线的情况。如图所示，总共可以架设 $3$ 条电线。

下图展示了第一次高度调整操作后（将第 $4$ 盏路灯高度改为 $6$）可架设电线的情况。如图所示，总共可以架设 $2$ 条电线。

下图展示了第二次高度调整操作后（将第 $6$ 盏路灯高度改为 $4$）可架设电线的情况。同样，总共可以架设 $2$ 条电线。

函数 count_cable 最终应返回 [3, 2, 2]。 该样例满足除子任务 4 以外的所有子任务条件。

Sample grader

Sample grader 按以下格式接收输入：

• 第 1 行：$N \ Q$
• 第 2 行：$A_1 \ A_2 \ \dots \ A_N$
• 第 $2 + i$ 行 ($1 \le i \le Q$)：$x_i \ h_i$

$(x_i, h_i)$ 表示第 $i$ 次高度调整操作 ($1 \le i \le Q$)。

Sample grader 按以下格式输出：

• 第 1 行：函数 count_cable 返回的数组

请注意，Sample grader 与实际评测时使用的评测程序不同。