На рельсах стоит \(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\) строк. В каждой строке выведите ответ для соответствующего набора входных данных.
Для каждого набора входных данных выведите \(m\) чисел: количество образовавшихся поездов после каждого сообщения.
Примечание
Для первого набора входных данных:
- Изначально массив \(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\) поезда.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|