Недавно, на свой день рождения, Алиса получила массив \(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\).
Помогите Алисе ответить на запросы Боба!
Выходные данные
Для каждого запроса \(2\)-го типа выведите одно целое число — ответ на данный запрос.
Примечание
Для первого запроса (\(l = 2\) и \(r = 5\)) неубывающие подмассивы \([p,q]\) — это \([2,2]\), \([3,3]\), \([4,4]\), \([5,5]\), \([2,3]\) и \([4,5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|