CF1690G.Count the Trains

There are $n$ of independent carriages on the rails. The carriages are numbered from left to right from $1$ to $n$. The carriages are not connected to each other. The carriages move to the left, so that the carriage with number $1$ moves ahead of all of them.

The $i$-th carriage has its own engine, which can accelerate the carriage to $a_i$ km/h, but the carriage cannot go faster than the carriage in front of it. See example for explanation.

All carriages start moving to the left at the same time, and they naturally form trains. We will call trains — consecutive moving carriages having the same speed.

For example, we have $n=5$ carriages and array $a = [10, 13, 5, 2, 6]$. Then the final speeds of the carriages will be $[10, 10, 5, 2, 2]$. Respectively, $3$ of the train will be formed.

There are also messages saying that some engine has been corrupted:

• message "k d" means that the speed of the $k$-th carriage has decreased by $d$ (that is, there has been a change in the maximum speed of the carriage $a_k = a_k - d$).

Messages arrive sequentially, the processing of the next message takes into account the changes from all previous messages.

After each message determine the number of formed trains.

铁轨上有 $n$ 节彼此独立的车厢。车厢从左到右依次编号为 $1$ 至 $n$，且车厢之间互不连接。所有车厢均向左行驶，其中编号为 $1$ 的车厢位于最前方。

第 $i$ 节车厢配备有独立引擎，可将其加速至 $a_i$ km/h；但该车厢的实际速度不能超过其前方（即编号更小）的车厢的速度。参见示例以进一步理解。

所有车厢同时开始向左运动，并自然形成若干“列车”。我们定义：列车为一组连续行驶且速度完全相同的车厢。

例如，当 $n = 5$，速度上限数组为 $a = [10, 13, 5, 2, 6]$ 时，各车厢最终实际速度为 $[10, 10, 5, 2, 2]$，因此共形成 $3$ 列列车。

此外，还会收到若干表示某引擎发生故障的消息：

• 消息 “k d” 表示第 $k$ 节车厢的引擎性能下降了 $d$（即其最大允许速度更新为 $a_k = a_k - d$）。

消息按顺序到达，处理后续消息时需考虑此前所有消息所引起的变化。

请在每次收到消息后，输出当前形成的列车数量。

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) —the number of input test cases.

This is followed by descriptions of the test cases.

The first line of each test case is empty.

The second line of the test case contains two integers $n$ and $m$ ($1 \le n,m \le 10^5$) —the number of carriages and the number of messages to slow down the carriage, respectively.

The third line contains $n$ integers: $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the number $a_i$ means that the carriage with number $i$ can reach a speed of $a_i$ km/h.

The next $m$ lines contain two integers $k_j$ and $d_j$ ($1 \le k_j \le n$, $0 \le d_j \le a_{k_j}$) —this is the message that the speed of the carriage with number $k_j$ has decreased by $d_j$. In other words, there has been a change in its maximum speed $a_{k_j} = a_{k_j} - d_j$. Note that at any time the speed of each carriage is non-negative. In other words, $a_i \ge s_i$, where $s_i$ —is the sum of such $d_j$ that $k_j=i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. Similarly, it is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示输入测试用例的数量。

随后是各测试用例的描述。

每个测试用例的第一行为一空行。

每个测试用例的第二行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 10^5$）——分别表示车厢数量和用于降低车厢速度的消息数量。

每个测试用例的第三行包含 $n$ 个整数：$a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）——其中 $a_i$ 表示编号为 $i$ 的车厢所能达到的最大速度（单位：km/h）。

接下来的 $m$ 行每行包含两个整数 $k_j$ 和 $d_j$（$1 \le k_j \le n$，$0 \le d_j \le a_{k_j}$）——表示一条消息：编号为 $k_j$ 的车厢的速度降低了 $d_j$。换言之，其最大速度被更新为 $a_{k_j} = a_{k_j} - d_j$。注意，在任意时刻，每节车厢的速度均非负。即对每个 $i$，均有 $a_i \ge s_i$，其中 $s_i$ 表示所有满足 $k_j = i$ 的 $d_j$ 值之和。

保证所有测试用例中 $n$ 的总和不超过 $10^5$；同理，保证所有测试用例中 $m$ 的总和不超过 $10^5$。

Print $t$ lines. On each line print the answer for the corresponding test case.

For each test case print $m$ numbers: the number of trains formed after each message.

输出 $t$ 行。每行输出对应测试用例的答案。

对每个测试用例，输出 $m$ 个数字：即在每条消息之后形成的列车数量。

For the first test case:

• Initially array $a = [6, 2, 3, 7]$.
• After the first message, the array $a = [6, 2, 1, 7]$. Accordingly, the speeds of the carriages are $[6, 2, 1, 1]$ and will form $3$ of the train.
• After the second message the array $a = [6, 2, 1, 0]$. Accordingly, the speeds of the carriages are $[6, 2, 1, 0]$, and $4$ of the train will be formed.

For the second test case:

• Initially, the array $a = [10, 13, 5, 2, 6]$.
• After the first message, the array $a = [10, 9, 5, 2, 6]$. Accordingly, the speeds of the carriages are equal: $[10, 9, 5, 2, 2]$, and $4$ of the train will be formed.
• After the second message the array $a = [10, 9, 5, 2, 4]$. Accordingly, the speeds of the carriages are $[10, 9, 5, 2, 2]$, and $4$ of the train will be formed.
• After the third message the array $a = [5, 9, 5, 2, 4]$. Accordingly, the speeds of the carriages are $[5, 5, 5, 2, 2]$, and $2$ of the train will be formed.
• After the fourth message the array $a = [5, 9, 3, 2, 4]$. Accordingly, the speeds of the carriages are $[5, 5, 3, 2, 2]$, and $3$ of the train will be formed.

对于第一个测试用例：

• 初始时数组 $a = [6, 2, 3, 7]$。
• 第一条消息后，数组 $a = [6, 2, 1, 7]$。相应地，车厢的速度为 $[6, 2, 1, 1]$，将组成 $3$ 节车厢的列车。
• 第二条消息后，数组 $a = [6, 2, 1, 0]$。相应地，车厢的速度为 $[6, 2, 1, 0]$，将组成 $4$ 节车厢的列车。

对于第二个测试用例：

• 初始时数组 $a = [10, 13, 5, 2, 6]$。
• 第一条消息后，数组 $a = [10, 9, 5, 2, 6]$。相应地，车厢的速度为 $[10, 9, 5, 2, 2]$，将组成 $4$ 节车厢的列车。
• 第二条消息后，数组 $a = [10, 9, 5, 2, 4]$。相应地，车厢的速度为 $[10, 9, 5, 2, 2]$，将组成 $4$ 节车厢的列车。
• 第三条消息后，数组 $a = [5, 9, 5, 2, 4]$。相应地，车厢的速度为 $[5, 5, 5, 2, 2]$，将组成 $2$ 节车厢的列车。
• 第四条消息后，数组 $a = [5, 9, 3, 2, 4]$。相应地，车厢的速度为 $[5, 5, 3, 2, 2]$，将组成 $3$ 节车厢的列车。