If you are experiencing an issue where math formulas are not displayed, please take the following steps.

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

Problem Statement

You are given an integer sequence $A$ of length $N$. The $i$-th value of the sequence $A$ is $A_i$.
You are given $Q$ queries of the following form; process them.

• In the $i$-th query, a pair of integers $L_i, R_i$ is given. Find the minimum value of the following function $f$.
• $\displaystyle f(x) = \sum_{k = L_i}^{R_i} |x - A_k|$

[Note] In this problem, even a correct solution may get TLE in slow languages such as Python [Sorry]

Input

$N\ Q$
$A_1\ A_2\ \cdots\ A_{N - 1}\ A_N$
$L_1\ R_1$
$\vdots$
$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$
• All input values are integers.

Output

Print $Q$ lines. On the $i$-th line, print the answer to query $i$ as an integer.

It can be proved that the minimum value is always an integer.

Sample

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