B. Алиса и парикмахер
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Волосы Алисы стали расти не по дням, а по минутам. Возможно, этому причиной является избыток витаминов, а возможно — чёрная магия...

Чтобы предотвратить это, Алиса решила сходить в парикмахерскую. При этом она хочет, чтобы после стрижки её волосы стали иметь длину не более $$$l$$$ сантиметров, где $$$l$$$ — её любимое число. Для наглядности будем считать, что голова Алисы представляет собой прямую линию, на которой последовательно растут $$$n$$$ волос. Давайте пронумеруем их от $$$1$$$ до $$$n$$$. За один взмах ножницами парикмахер может укоротить все волосы на любом отрезке до длины $$$l$$$, но с одним условием: все волосы на этом отрезке изначально имели длину строго больше $$$l$$$. Парикмахер хочет сделать свою работу как можно скорее, поэтому сделает минимальное число взмахов ножницами, так как каждый взмах занимает одну секунду.

Алиса пока ещё не решила, когда пойдёт в парикмахерскую, поэтому попросила вас посчитать время её стрижки в разные моменты времени. В частности, вам нужно обрабатывать два типа запросов:

  • $$$0$$$ — Алиса интересуется сколько времени займёт стрижка если она прямо сейчас пойдёт в парикмахерскую.
  • $$$1$$$ $$$p$$$ $$$d$$$ — $$$p$$$-й волос вырос на $$$d$$$ сантиметров.

Обратите внимание, что в запросе $$$0$$$ Алису интересует гипотетический сценарий стрижки волос — длина волос после этого не изменяется.

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$l$$$ ($$$1 \le n, m \le 100\,000$$$, $$$1 \le l \le 10^9$$$) — количество волос, количество запросов и любимое число Алисы.

Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — исходные длины волос Алисы.

Каждая из следующих $$$m$$$ строк содержит очередной запрос в формате описанном в условии.

Описание запроса начинается с целого числа $$$t_i$$$. Если $$$t_i = 0$$$, то необходимо узнать время стрижки. Иначе $$$t_i = 1$$$ и в этот момент вырастает волос. Тогда на той же строке даны ещё два целых числа: $$$p_i$$$ и $$$d_i$$$ ($$$1 \le p_i \le n$$$, $$$1 \le d_i \le 10^9$$$) — номер волоса и длина, на которую он вырастает.

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

Для каждого запроса типа $$$0$$$ выведите время стрижки Алисы.

Пример
Входные данные
4 7 3
1 2 3 4
0
1 2 3
0
1 1 3
0
1 3 1
0
Выходные данные
1
2
2
1
Примечание

Рассмотрим пример из условия:

  • Изначально длины волос равны $$$1, 2, 3, 4$$$ и только $$$4$$$-й волос длиннее $$$l=3$$$, и парикмахер может укоротить его за $$$1$$$ секунду.
  • Затем у Алисы подрастает второй волос, и длины волос теперь равны $$$1, 5, 3, 4$$$
  • Теперь стрижка занимает две секунды: требуется два взмаха ножницами — на $$$4$$$-й волос и на $$$2$$$-й.
  • Затем у Алисы подрастает первый волос, и длины волос теперь равны $$$4, 5, 3, 4$$$
  • Стрижка всё ещё занимает две секунды: за один взмах парикмахер может состричь $$$4$$$-й волос и за ещё один отрезок с $$$1$$$-го по $$$2$$$-й волос.
  • Затем у Алисы подрастает третий волос, и длины волос теперь равны $$$4, 5, 4, 4$$$
  • Теперь стрижка занимает всего одну секунду: за один взмах можно укоротить подотрезок с $$$1$$$-го волоса по $$$4$$$-й.