정적 구간 역전 쿼리

길이가 $N$인 정수 수열 $(A_0, A_1, \ldots, A_{N-1})$이 주어진다. 다음 $Q$개의 쿼리를 순서대로 처리한다.

• $l_i$ $r_i$: $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i-1})$의 역전의 개수를 출력한다

수열 $(B_0, B_1, \ldots, B_{M-1})$에서 역전이란 $0 \leq i < j \lt M$이고 $B_i \gt B_j$인 인덱스의 쌍 $(i, j)$을 말한다.

제약 조건

• $1 \leq N \leq 100000$
• $1 \leq Q \leq 100000$
• $0 \leq A_i \leq 1000000000$
• $0 \leq l_i \lt r_i \leq N$

$N$ $Q$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$l_0$ $r_0$
$l_1$ $r_1$
$\vdots$
$l_{Q-1}$ $r_{Q-1}$

$l_i$ $r_i$: $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i-1})$의 역전의 개수를 출력한다