311280: CF1959H. Count the Trains

H. Count the Trainstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

3


4 2
6 2 3 7
3 2
4 7


5 4
10 13 5 2 6
2 4
5 2
1 5
3 2


13 4
769 514 336 173 181 373 519 338 985 709 729 702 168
12 581
6 222
7 233
5 117

Output

3 4 
4 4 2 3 
5 6 6 5 

Note

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.

题目大意：
有n节独立的马车在铁轨上，从左到右编号为1到n。这些马车之间没有连接。所有马车都向左移动，编号1的马车在最前面。每节马车有自己的引擎，可以加速到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）。信息按顺序到达，处理下一条信息时要考虑之前所有信息的变化。在每条信息后，确定形成的火车数量。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4），表示输入的测试用例数。
接下来是t个测试用例的描述。
每个测试用例的第一行是空的。
第二行包含两个整数n和m（1≤n,m≤10^5），分别表示马车的数量和减速信息数量。
第三行包含n个整数：a_1,a_2,…,a_n（0≤a_i≤10^9），a_i表示第i节马车可以达到的速度。
接下来m行，每行包含两个整数k_j和d_j（1≤k_j≤n，0≤d_j≤a_{k_j}），表示第k_j节马车的速度降低了d_j。即最大速度从a_{k_j}变为a_{k_j}-d_j。在任何时候，每节马车的速度都是非负的。即a_i≥s_i，其中s_i是所有满足k_j=i的d_j之和。
保证所有测试用例的n之和不超过10^5，m之和也不超过10^5。

输出：
打印t行，每行对应一个测试用例的答案。
对于每个测试用例，打印m个数字：每条信息后形成的火车数量。题目大意： 有n节独立的马车在铁轨上，从左到右编号为1到n。这些马车之间没有连接。所有马车都向左移动，编号1的马车在最前面。每节马车有自己的引擎，可以加速到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）。信息按顺序到达，处理下一条信息时要考虑之前所有信息的变化。在每条信息后，确定形成的火车数量。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4），表示输入的测试用例数。 接下来是t个测试用例的描述。 每个测试用例的第一行是空的。 第二行包含两个整数n和m（1≤n,m≤10^5），分别表示马车的数量和减速信息数量。 第三行包含n个整数：a_1,a_2,…,a_n（0≤a_i≤10^9），a_i表示第i节马车可以达到的速度。 接下来m行，每行包含两个整数k_j和d_j（1≤k_j≤n，0≤d_j≤a_{k_j}），表示第k_j节马车的速度降低了d_j。即最大速度从a_{k_j}变为a_{k_j}-d_j。在任何时候，每节马车的速度都是非负的。即a_i≥s_i，其中s_i是所有满足k_j=i的d_j之和。 保证所有测试用例的n之和不超过10^5，m之和也不超过10^5。 输出： 打印t行，每行对应一个测试用例的答案。 对于每个测试用例，打印m个数字：每条信息后形成的火车数量。