You are given a sequence of integers $x_1, x_2, \ldots, x_n$. Consider the weighted undirected graph $G$ on $n$ vertices, numbered $1$ through $n$, that contains, for every pair of vertices $u$ and $v$ with $u < v$, the edge $\{u, v\}$ of weight $x_v - x_u$.

Note that $x$ is not necessarily sorted, so edge weights may be negative.

For a pair $(\ell, r)$ with $\ell \le r$, let $G[\ell, r]$ denote the subgraph of $G$ induced by the vertices $\ell, \ell + 1, \ldots, r$; that is, the graph on those vertices keeping exactly the edges of $G$ with both endpoints in that range. Define $f(\ell, r)$ as the minimum possible total weight of a spanning tree of $G[\ell, r]$. In particular, $f(\ell, \ell) = 0$.

You are given $q$ pairs $(\ell, r)$. Compute $f(\ell, r)$ for each of them.

Input

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$): the length of the sequence and the number of queries.

The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ ($-10^9 \le x_i \le 10^9$).

Each of the next $q$ lines contains two integers $\ell$ and $r$ ($1 \le \ell \le r \le n$) describing one query.

Output

Print $q$ lines. The $i$-th line must contain a single integer: the answer to the $i$-th query.

Examples

Input 1

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

Output 1

-10
10
-10
0

Note

For the first query, the three edge weights are $10$, $0$, and $-10$. Choosing the edges of weights $0$ and $-10$ gives a spanning tree of total weight $-10$.

The second and third queries contain two vertices, so their answers are the weights of their only edges: $10$ and $-10$, respectively. The final query contains one vertex and therefore has answer $0$.