题目描述

在一条笔直的光纤干线上，从左向右依次分布着 $n$ 个网络枢纽，第 $i$ 个枢纽的位置坐标为 $x_i$。已知坐标严格递增，即 $x_1 < x_2 < \cdots < x_n$。

现在需要进行 $q$ 次网络扩建规划。每次规划选定第 $l$ 个枢纽作为核心枢纽，并向其右侧（包含自身）的第 $l, l+1, \ldots, r$ 个枢纽分别架设一条独立的专线。

对于任意一个目标枢纽 $i$，从核心枢纽 $l$ 向其架设的专线长度即为两地的坐标距离 $x_i - x_l$。

请你计算，对于每一次规划，将所有专线长度求和，得到的总施工长度是多少？

输入格式

第一行输入两个整数 $n, q$，分别表示枢纽数量和规划查询的次数。

第二行输入 $n$ 个整数 $x_1, x_2, \ldots, x_n$，表示各枢纽的坐标。

接下来 $q$ 行，每行输入两个整数 $l, r$，表示一次规划的查询范围。

输出格式

对于每一次规划，输出一行一个整数，表示此次规划所需的专线总长度。

样例

5 3
2 5 9 14 20
1 3
2 5
4 4

10
28
0

样例解释

• 第一次规划：核心枢纽为 $1$（坐标 $2$），连接枢纽 $1, 2, 3$。 总长度 $= (2-2) + (5-2) + (9-2) = 0 + 3 + 7 = 10$，也就相当于 $2+5+9 - 2*3 = 10$。
• 第二次规划：核心枢纽为 $2$（坐标 $5$），连接枢纽 $2, 3, 4, 5$。 总长度 $= (5-5) + (9-5) + (14-5) + (20-5) = 0 + 4 + 9 + 15 = 28$。
• 第三次规划：核心枢纽为 $4$（坐标 $14$），仅连接自身。 总长度 $= 14 - 14 = 0$。

数据范围

对于 $30\%$ 的数据，满足 $1 \le n,q \le 2000$。

对于 $100\%$ 的数据，满足 $1 \le n,q \le 2 \times 10^5$，$1 \le x_i \le 10^9$，$x_1 < x_2 < \cdots < x_n$，$1 \le l \le r \le n$。