# Static Range Inversions Query

AC一覧

## Problem Statement問題文

You are given an integer sequence $(A_0, A_1, \ldots, A_{N-1})$ with the length $N$. Process the following $Q$ queries in order.

• $l_i$ $r_i$: Print the number of inversions in $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i-1})$

An inversion in a sequence $(B_0, B_1, \ldots, B_{M-1})$ is a pair of indices $(i, j)$ such that $0 \leq i < j \lt M$ and $B_i \gt B_j$.

• $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)$の個数です。

## Constraints制約

• $1 \leq N \leq 100{,}000$
• $1 \leq Q \leq 100{,}000$
• $0 \leq A_i \leq 10^{9}$
• $0 \leq l_i \lt r_i \leq N$

## Input入力

$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}$


## Sampleサンプル

### # 1

4 2
4 1 4 0
1 3
0 4

0
4


Timelimit: 5 secs

Before submitting, please confirm terms and conditions