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

Недавно, на свой день рождения, Алиса получила массив $$$a_1, a_2, \dots, a_n$$$. Массив ей очень понравился, как ее другу Бобу, которому Алиса его показала.

Однако довольно скоро Боб, как любой хороший друг, попросил Алису выполнить $$$q$$$ операций двух видов над ее массивом:

  • $$$1$$$ $$$x$$$ $$$y$$$: присвоить элементу $$$a_x$$$ значение $$$y$$$ (или $$$a_x = y$$$);
  • $$$2$$$ $$$l$$$ $$$r$$$: посчитать, сколько неубывающих подмассивов содержится в подмассиве $$$[a_l, a_{l+1}, \dots, a_r]$$$. Формально, нужно посчитать количество пар индексов $$$(p,q)$$$ таких, что $$$l \le p \le q \le r$$$ и $$$a_p \le a_{p+1} \le \dots \le a_{q-1} \le a_q$$$.

Помогите Алисе ответить на запросы Боба!

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

В первой строке заданы два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — размер массива и количество запросов, соответственно.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив Алисы.

В следующих $$$q$$$ строках заданы по три целых числа. Первое число в $$$i$$$-й строке — это $$$t_i$$$, тип операции $$$i$$$-го запроса ($$$t_i = 1$$$ или $$$t_i = 2$$$).

Если $$$t_i = 1$$$, то следующие два числа — это $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le 10^9$$$), позиция $$$x_i$$$ и новое значение $$$y_i$$$ (нужно присвоить $$$a_{x_i} = y_i$$$).

Если $$$t_i = 2$$$, то следующие два числа — это $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$), границы подмассива, о котором Боб спрашивает Алису в $$$i$$$-м запросе.

Гарантируется, что есть хотя бы один запрос второго типа.

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

Для каждого запроса $$$2$$$-го типа выведите одно целое число — ответ на данный запрос.

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

Для первого запроса ($$$l = 2$$$ и $$$r = 5$$$) неубывающие подмассивы $$$[p,q]$$$ — это $$$[2,2]$$$, $$$[3,3]$$$, $$$[4,4]$$$, $$$[5,5]$$$, $$$[2,3]$$$ и $$$[4,5]$$$.