CF1567E.Non-Decreasing Dilemma

Alice has recently received an array $a_1, a_2, \dots, a_n$ for her birthday! She is very proud of her array, and when she showed her friend Bob the array, he was very happy with her present too!

However, soon Bob became curious, and as any sane friend would do, asked Alice to perform $q$ operations of two types on her array:

• $1$ $x$ $y$: update the element $a_x$ to $y$ (set $a_x = y$).
• $2$ $l$ $r$: calculate how many non-decreasing subarrays exist within the subarray $[a_l, a_{l+1}, \dots, a_r]$. More formally, count the number of pairs of integers $(p,q)$ such that $l \le p \le q \le r$ and $a_p \le a_{p+1} \le \dots \le a_{q-1} \le a_q$.

Help Alice answer Bob's queries!

爱丽丝最近在生日时收到了一个数组 $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]$ 中非递减子数组的个数。更准确地说，统计满足 $l \le p \le q \le r$ 且 $a_p \le a_{p+1} \le \dots \le a_{q-1} \le a_q$ 的整数对 $(p,q)$ 的数量。

请帮助爱丽丝回答鲍勃的查询！

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the size of the array, and the number of queries, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of Alice's array.

The next $q$ lines consist of three integers each. The first integer of the $i$-th line is $t_i$, the operation being performed on the $i$-th step ($t_i = 1$ or $t_i = 2$).

If $t_i = 1$, the next two integers are $x_i$ and $y_i$ ($1 \le x_i \le n$; $1 \le y_i \le 10^9$), updating the element at position $x_i$ to $y_i$ (setting $a_{x_i} = y_i$).

If $t_i = 2$, the next two integers are $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$), the two indices Bob asks Alice about for the $i$-th query.

It's guaranteed that there is at least one operation of the second type.

第一行包含两个整数 $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$ 的操作。

For each query of type $2$, print a single integer, the answer to the query.

对于每个类型为 $2$ 的查询，输出一个整数，即该查询的答案。

For the first query, $l = 2$ and $r = 5$, and the non-decreasing subarrays $[p,q]$ are $[2,2]$, $[3,3]$, $[4,4]$, $[5,5]$, $[2,3]$ and $[4,5]$.

对于第一个查询，$l = 2$ 且 $r = 5$，非递减子数组 $[p,q]$ 为 $[2,2]$、$[3,3]$、$[4,4]$、$[5,5]$、$[2,3]$ 和 $[4,5]$。