数式が表示されない不具合が発生している場合は次の対応をお願いします．

https://twitter.com/yukicoder/status/1191757446596812800?s=20

問題文

長さ $N$ の整数列 $A$ が与えられます，数列 $A$ の $i$ 番目の値は $A_i$ です．
以下の形式のクエリが $Q$ 個与えられるので，処理してください．

• $i$ 番目のクエリでは整数の組 $L_i,R_i$ が与えられるので，以下の関数 $f$ の最小値を求めてください．
• ${\displaystyle f(x)=\sum _{k=L_i}^{R_i}|x-A_k|}$

[注意] この問題では正しい解法だとしても，Python などの低速な言語では TLE になる可能性があります[ごめんなさい]

入力

$NQ$
$A_1{A}_2\cdots A_{N-1}{A}_N$
$L_1{R}_1$
$⋮$
$L_Q{R}_Q$

• $1\le N,Q\le 2\times {10}^5$
• $-{10}^9\le A_i\le {10}^9$
• $1\le L_i\le R_i\le N$
• 入力はすべて整数．

出力

$Q$ 行出力し $i$ 行目にはクエリ $i$ の答えを整数で一行に出力してください．

なお最小値が必ず整数であることが証明出来ます．

サンプル

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

6
2
1
2
2

5 3
1 3 3 3 3
1 3
3 3
3 3

2
0
0

20 10
-574 627 212 956 -285 161 -331 -107 -229 -87 -414 -917 842 835 566 117 -298 -608 -964 -182
2 10
9 10
11 12
4 12
19 19
6 17
14 15
1 13
5 13
16 20

2908
142
503
2870
0
4730
269
5461
2756
1507