整数列 $x_1, x_2, \ldots, x_n$ が与えられます。$1$ から $n$ までの番号が付いた $n$ 個の頂点を持つ重み付き無向グラフ $G$ を考えます。このグラフには、$u < v$ を満たすすべての頂点の組 $u, v$ に対して、重み $x_v - x_u$ の辺 $\{u, v\}$ があります。

$x$ は必ずしもソートされていないため、辺の重みが負になる場合があることに注意してください。

$\ell \le r$ を満たす組 $(\ell, r)$ に対して、$G[\ell, r]$ を、頂点 $\ell, \ell + 1, \ldots, r$ によって誘導される $G$ の部分グラフとします。つまり、これらの頂点からなるグラフで、両端点がこの範囲にある $G$ の辺をすべて残したものです。$f(\ell, r)$ を、$G[\ell, r]$ の全域木の重みの総和として可能な最小値と定義します。特に、$f(\ell, \ell) = 0$ です。

$q$ 個の組 $(\ell, r)$ が与えられます。それぞれについて $f(\ell, r)$ を求めてください。

入力

1 行目には、整数列の長さとクエリの個数を表す 2 つの整数 $n$ と $q$ ($1 \le n, q \le 2 \cdot 10^5$) が与えられます。

2 行目には、$n$ 個の整数 $x_1, x_2, \ldots, x_n$ ($-10^9 \le x_i \le 10^9$) が与えられます。

続く $q$ 行には、それぞれ 1 つのクエリを表す 2 つの整数 $\ell$ と $r$ ($1 \le \ell \le r \le n$) が与えられます。

出力

$q$ 行出力してください。$i$ 行目には、$i$ 番目のクエリに対する答えを表す整数を 1 つ出力してください。

入出力例

入力 1

3 4
0 10 0
1 3
1 2
2 3
2 2

出力 1

-10
10
-10
0

注記

最初のクエリでは、3 本の辺の重みは $10$、$0$、$-10$ です。重みが $0$ と $-10$ の辺を選ぶと、重みの総和が $-10$ の全域木が得られます。

2 番目と 3 番目のクエリには 2 個の頂点が含まれるため、答えはそれぞれ唯一の辺の重みである $10$ と $-10$ です。最後のクエリには 1 個の頂点が含まれるため、答えは $0$ です。