Description

Yoshino gives you a sequence of length $n$, where the $i$-th term is $a_i$.

Now Yoshino will perform $m$ operations on the sequence.

There are two types of operations:

• $1\ l\ r\ x$: Yoshino changes the numbers with indices in the interval $[l,r]$ into an arithmetic progression starting from $x$ with common difference $1$.

• $2$: Yoshino needs to query the number of inversion pairs in the entire sequence. An inversion pair is a pair $(i,j)$ such that $i<j$ and $a_i>a_j$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers; the $i$-th one is $a_i$.

The next $m$ lines each describe an operation, with the meaning as stated above.

Output Format

For each query, output one integer per line as the answer.

3 3
3 2 1 
2 
1 1 3 1 
2 

3 
0 

Hint

[Sample Explanation]

The first operation is a query. At this time there are three inversion pairs: $(1,3),(2,3),(1,2)$, so the answer is $3$.

After the second operation (the modification), the sequence becomes $1\ 2\ 3$.

The third operation is a query. At this time there are no inversion pairs in the sequence, so the answer is $0$.

You can get more samples here.

[Constraints]

This problem uses bundled testdata.

For all testdata, $1\le n,m,a_i\le 3\times 10^4$, $1\le l\le r\le n$, $1\le x\le 3\times 10^4-r+l$.

Translated by ChatGPT 5