G. Посчитай поезда
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На рельсах стоит $$$n$$$ автономных вагончиков. Вагончики пронумерованы слева направо от $$$1$$$ до $$$n$$$. Вагончики между собой не сцеплены. При этом вагончики движутся влево, так что вагончик с номером $$$1$$$ движется впереди всех.

У $$$i$$$-го вагончика есть свой двигатель, который может разогнать вагончик до $$$a_i$$$ км/ч, но при этом, вагончик не может ехать быстрее, чем вагончик перед ним. Для пояснения смотрите пример.

Все вагончики одновременно начинают двигаться влево, при этом, естественно образуются поезда. Будем называть поездом — подряд движущиеся вагончики, имеющие одинаковую скорость.

Например, у нас есть $$$n=5$$$ вагончиков и массив $$$a = [10, 13, 5, 2, 6]$$$. Тогда итоговые скорости вагончиков будут равны: $$$[10, 10, 5, 2, 2]$$$. Соответственно, будет образовано $$$3$$$ поезда.

Также приходят сообщения о том, что какой-то двигатель был испорчен:

  • cообщение «k d» означает, что скорость $$$k$$$-го вагончика уменьшилась на $$$d$$$ (то есть произошло изменение максимальной скорости вагончика $$$a_k = a_k - d$$$).

Сообщения приходят последовательно, при обработке очередного сообщения учитываются изменения от всех предыдущих сообщений.

После каждого сообщения определите количество образовавшихся поездов.

Входные данные

В первой строке входных данных записано единственное целое число $$$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$$$ может развивать скорость до $$$a_i$$$ км/ч.

В следующих $$$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$$$. Обратите внимание, что в любой момент времени скорость каждого вагончика неотрицательна. Иными словами, $$$a_i \ge s_i$$$, где $$$s_i$$$ — это сумма таких $$$d_j$$$, что $$$k_j=i$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$. Аналогично гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превышает $$$10^5$$$.

Выходные данные

Выведите $$$t$$$ строк. В каждой строке выведите ответ для соответствующего набора входных данных.

Для каждого набора входных данных выведите $$$m$$$ чисел: количество образовавшихся поездов после каждого сообщения.

Пример
Входные данные
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
Выходные данные
3 4 
4 4 2 3 
5 6 6 5
Примечание

Для первого набора входных данных:

  • Изначально массив $$$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$$$ поезда.