Rainy Valley's Subarray Query

You are given a sequence \(a_1, a_2, \dots, a_n\) of length \(n\). For any interval \([l, r]\) (with \(1 \le l \le r \le n\)), define its subintervals as all intervals \([l', r']\) such that \(l \le l' \le r' \le r\). In other words, every contiguous subarray of \([l,r]\) is considered a subinterval.

You need to perform \(m\) operations. There are two types of operations:

• Update: 1 x y — Update the value at position \(x\) to \(y\). Formally, set \(a_x = y\).
• Query: 2 l r x — For the subarray \([l, r]\), count how many of its subintervals have a maximum value \(\le x\). That is, count the number of subintervals \([l',r']\) (with \(l \le l' \le r' \le r\)) such that \[ \max(a_{l'}, a_{l'+1}, \dots, a_{r'}) \le x. \]

Note that there is no output for update operations. For each query operation, output the corresponding number on a new line.

inputFormat

The first line contains two integers \(n\) and \(m\) — the length of the sequence and the number of operations.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), representing the initial sequence.

Each of the next \(m\) lines describes an operation in one of the following formats:

• 1 x y — update operation.
• 2 l r x — query operation.

It is guaranteed that the operations are valid.

outputFormat

For each query operation (i.e. operations of type 2), output a single line containing the number of subintervals in the interval \([l, r]\) whose maximum value is at most \(x\).

sample

5 5
1 2 3 4 5
2 1 5 3
1 3 1
2 1 5 3
1 5 0
2 1 5 3

6
6
7