Description

Amagai Kosame gives you a sequence of length $n$. Define the sub-intervals of an interval $[l,r]$ as all intervals of the form $[l',r']$, where $l',r'$ are integers and $l \le l' \le r' \le r$.

There are $m$ operations:

1 x y: Modify the value at position $x$ to $y$.

2 l r x: Query how many sub-intervals in $[l,r]$ have maximum value less than or equal to $x$.

Input Format

The first line contains two integers $n,m$. The second line contains $n$ integers representing the sequence.

Then follow $m$ lines, each in the form 1 x y or 2 l r x, describing each operation.

Output Format

For each operation of type 2, output one line with one number, representing the answer.

6 6
1 1 4 5 1 4
1 1 4
2 1 4 2
2 1 1 4
2 1 5 4
1 5 4 
2 3 3 3

1
1
7
0

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078

For $100\%$ of the testdata, $n,m \le 3 \times 10^5$, $1 \le l \le r \le n$, $1 \le x, y \le n$, each element in the sequence is in $[1,n]$, and all numbers are integers.

Translated by ChatGPT 5