Волосы Алисы стали расти не по дням, а по минутам. Возможно, этому причиной является избыток витаминов, а возможно — чёрная магия...
Чтобы предотвратить это, Алиса решила сходить в парикмахерскую. При этом она хочет, чтобы после стрижки её волосы стали иметь длину не более \(l\) сантиметров, где \(l\) — её любимое число. Для наглядности будем считать, что голова Алисы представляет собой прямую линию, на которой последовательно растут \(n\) волос. Давайте пронумеруем их от \(1\) до \(n\). За один взмах ножницами парикмахер может укоротить все волосы на любом отрезке до длины \(l\), но с одним условием: все волосы на этом отрезке изначально имели длину строго больше \(l\). Парикмахер хочет сделать свою работу как можно скорее, поэтому сделает минимальное число взмахов ножницами, так как каждый взмах занимает одну секунду.
Алиса пока ещё не решила, когда пойдёт в парикмахерскую, поэтому попросила вас посчитать время её стрижки в разные моменты времени. В частности, вам нужно обрабатывать два типа запросов:
- \(0\) — Алиса интересуется сколько времени займёт стрижка если она прямо сейчас пойдёт в парикмахерскую.
- \(1\) \(p\) \(d\) — \(p\)-й волос вырос на \(d\) сантиметров.
Обратите внимание, что в запросе \(0\) Алису интересует гипотетический сценарий стрижки волос — длина волос после этого не изменяется.