Новый архитектор Арракиса проектирует новый городоской квартал Арракина, состоящий из $$$n$$$ расположенных в ряд зданий. Здание номер $$$i$$$ имеет ровно $$$h_i$$$ этажей.
Теперь архитектору интересно, смогут ли горожане по достоинству оценить его проект. Проблема в том, что в городе часто случаются песчаные бури, а стены города защищают от них только нижние этажи, поэтому верхние этажи некоторых зданий может быть не видно с земли.
Формально, вам поступают запросы вида $$$(l, r, f)$$$ — «уровень песчаной бури вокруг зданий с $$$l$$$-го по $$$r$$$-й включительно становится равен $$$f$$$». Это означает, что у всех зданий с $$$l$$$-го по $$$r$$$-й становится видно только первые $$$f$$$ этажей, тогда как все этажи выше спрятаны за песком и не видны. После каждого такого запроса вы должны сообщить архитектору, сколько всего этажей всех его зданий видно с земли.
Еще раз отметим, что песчаная буря непрерывна вверх, то есть если этаж номер $$$x$$$ здания номер $$$y$$$ спрятан за песком, то этажи $$$x + 1, x + 2, \ldots, h_y$$$ также спрятаны, и видны только этажи с первого по $$$(x - 1)$$$-й.
Изначально, перед поступлением первого запроса, песчаная буря еще не началась, то есть все здания видны целиком.
В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$q$$$ — количество зданий и количество запросов на изменение уровня песчаной бури ($$$1 \le n, q \le 10^5$$$).
Во второй строке ввода через пробел перечислены $$$n$$$ целых чисел $$$h_i$$$ — высоты зданий ($$$1 \le h_i \le 10^9$$$).
В следующих $$$q$$$ строках даны описания запросов. В $$$i$$$-й из них через пробел даны числа $$$l_i$$$, $$$r_i$$$ и $$$f_i$$$ — границы отрезка, на котором меняется уровень песчаной бури, и сам новый уровень ($$$1 \le l_i \le r_i \le n$$$; $$$0 \le f_i \le 10^9$$$).
Выведите $$$q$$$ строк, каждая из которых содержит единственное целое число — ответ на соответствующий запрос.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
0 | – | примеры из условия | полная | |
1 | 10 | все $$$h_i$$$ равны, запросы не пересекаются | полная | |
2 | 13 | $$$h_{i + 1} \ge h_i$$$, запросы не пересекаются | 1 | первая ошибка |
3 | 15 | $$$n, q \le 200$$$ | 0 | первая ошибка |
4 | 17 | $$$r_i - l_i \le 10$$$ для всех $$$i$$$ | 0 | первая ошибка |
5 | 20 | $$$n, q \le 2000$$$ | 0, 3 | первая ошибка |
6 | 25 | нет | 0 – 5 | первая ошибка |
1 3 100 1 1 50 1 1 120 1 1 0
50 100 0
4 5 1 5 7 3 1 3 1 2 4 2 2 3 5 1 4 3 3 4 100
6 7 13 10 14