注意

この問題の実行制限時間は7sです。
また、高速な言語の使用を推奨します。（C++及びJavaでのACを確認しています。）

問題文

長さ $N$ の数列 $A = \{a_i\}$ が与えられます。
$Q$ 個のクエリに答えてください。それぞれのクエリは以下の形式で与えられます。

• $l \ r$

  • $a_l,a_{l+1},\dots,a_r$ を $1$ 以上 $N$ 以下の好きな整数に変更するときの $A$ の転倒数の最小値を求める。
  • 各要素は別々の値に変更でき、全て同じ値にする必要はありません。また、変更前と同じ値でも構いません。

$A$ の転倒数とは、$a_i > a_j$ を満たす $(i,j) \ (1 \leq i < j \leq N)$ の個数です。またそれぞれのクエリは独立しており、 変更した数列は毎回元に戻ることに注意してください。

入力

$N\ Q$
$a_1 \dots a_N$
$l_1 \ r_1$
$\vdots$
$l_Q \ r_Q$

• 入力は全て整数
• $1 \leq N,Q \leq 2 \times 10^4$
• $1 \leq a_i \leq N$
• $1 \leq l_i \leq r_i \leq N$

出力

$i$ 行目に $i$ 番目のクエリの解を出力してください。

サンプル

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

4
2
0

4 4
4 3 2 1
1 1
2 2
3 3
4 4

3
4
4
3

10 10
9 7 7 10 9 8 1 3 2 9
5 6
3 9
3 10
2 5
8 9
6 8
1 2
2 4
10 10
2 7

24
1
1
12
15
15
17
15
25
9