Background

"Becoming a Spirit did make me go through many painful things, and many sad things. But—I've also gained far more happiness and joy than all that pain and sorrow."

"—I think that although Mio wanted to use my life, in exchange, didn't she also let me live for a longer time?"

"By the way—almost forgot. Yotsuba, ... can you spare a little while?"

"Then, let me introduce you properly—Mom."

"This is Natsumi, my—most important friend."

"This is Shido, the person I—like the most."

Problem 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