题目描述

一条直线上有 $n$ 个通信节点，第 $i$ 个节点的位置为 $x_i$ 。这些节点从左到右依次排列，并满足：

x_1 < x_2 < \cdots < x_n

现在有 $q$ 次建设方案。每次方案给出两个整数 $l,r$ ，表示要以第 $l$ 个节点作为主节点，分别向第 $l,\ l+1,\ \ldots,\ r$ 个节点铺设独立通信线路。

每一条线路都是从主节点单独连接到对应节点，因此第 $i$ 个节点所需线路长度为：

x_i-x_l

请你计算每次方案中，所有独立线路的总长度：

(x_l-x_l)+(x_{l+1}-x_l)+\cdots+(x_r-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$ 个节点为主节点，分别向第 $1,2,3$ 个节点铺设线路：

(2-2)+(5-2)+(9-2)=0+3+7=10

也就是相当于 $2+5+9 - 2*3 = 10$

第二次方案中，以第 $2$ 个节点为主节点，分别向第 $2,3,4,5$ 个节点铺设线路：

(5-5)+(9-5)+(14-5)+(20-5)=0+4+9+15=28

第三次方案中，只连接第 $4$ 个节点自身，线路长度为 $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$ 。