给定一个整数序列 $x_1,x_2,\ldots,x_n$。考虑一个有 $n$ 个顶点的带权无向图 $G$，顶点编号为 $1$ 到 $n$。对于每一对满足 $u<v$ 的顶点 $u$ 和 $v$，图中都有一条权值为 $x_v-x_u$ 的边 $\{u,v\}$。

注意，$x$ 不一定有序，因此边权可能为负。

对于满足 $\ell\le r$ 的一对 $(\ell,r)$，用 $G[\ell,r]$ 表示 $G$ 中由顶点 $\ell,\ell+1,\ldots,r$ 诱导的子图；也就是说，这个图的顶点为上述顶点，并且恰好保留 $G$ 中两个端点都在该范围内的边。定义 $f(\ell,r)$ 为 $G[\ell,r]$ 的生成树可能达到的最小总权值。特别地，$f(\ell,\ell)=0$。

给定 $q$ 对 $(\ell,r)$。请计算每一对对应的 $f(\ell,r)$。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le 2\cdot 10^5$），分别表示序列的长度和询问的数量。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$（$-10^9\le x_i\le 10^9$）。

接下来的 $q$ 行，每行包含两个整数 $\ell$ 和 $r$（$1\le\ell\le r\le n$），描述一个询问。

输出格式

输出 $q$ 行。第 $i$ 行必须包含一个整数，表示第 $i$ 个询问的答案。

样例

输入格式 1

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

输出格式 1

-10
10
-10
0

说明

对于第一个询问，三条边的权值分别为 $10$、$0$ 和 $-10$。选择权值为 $0$ 和 $-10$ 的边，就能得到一棵总权值为 $-10$ 的生成树。

第二个和第三个询问各包含两个顶点，因此它们的答案就是各自唯一一条边的权值，分别为 $10$ 和 $-10$。最后一个询问包含一个顶点，因此答案为 $0$。