---
# System prepended metadata

title: Protect The Princess

---

# Protect The Princess
There is a lovely princess named My in the Wind Kingdom, who is the third daughter of the King. The King desires to find a husband for his daughter and announces that whoever find the flying horse will be able to marry her. Unfortunately, the princess is kidnapped by a dragon, causing great worry to the King. Consequently, the King modifies the conditions of the marriage proposal, stating that whoever rescues the princess by killing the dragon will win her hand in marriage. Joon, who has fallen in love with the princess, begins searching for the dragon immediately.

To save the princess, the dragon gives Joon an array with $n$ elements $a_1, a_2, ..., a_n$ and then it will perform $q$ operations of two following types:

* $1$ $u$ $v$: update the element $a_u$ to $v$ (or set $a_u=v$).
* $2$ $l$ $r$: calculate how many non-decreasing subarrays exist within the subarray $[a_l, a_{l+1}, ..., a_r]$. In other words, let's count the number of pairs of integer ($x$, $y$) such that $l \le x \le y \le r$ and $a_x \le a_{x+1} \le ... \le a_{y-1} \le a_y$.


Now let's imagine you are Joon, please save the princess by answering the dragon's queries!

## Input
* The first line contains two integers $n$ and $q$ $(1 \le n, q \le 2.10^5)$ - the size of the array and the number of queries.
* The second line contains $n$ integer $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ - the elements of the dragon'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$ (set $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.

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

## Example
### Input
5 6
5 3 6 3 7
2 2 5
2 1 3
1 4 6
2 2 5
1 2 8
2 2 5
### Output
6
4
10
7
