老 M 是一个知名的混元形意太极大师，经常会有仰慕者前来拜师学艺，但他们必须经过严格的入学考试：爬楼梯。

老 M 的道场有 $n$ 个平台排成一列，第 $i$ 个平台的高度为 $h_i$，从第 $i$ 个平台爬楼梯到第 $i+1$ 个平台所需要消耗的体力为 $|h_i-h_{i+1}|$。

当第 $j$ 个仰慕者来拜师学艺时，老 M 会指定一个区间 $[l_j, r_j]$，取出这个区间内的所有平台，并使用内功将他们重新排列（不改变原序列），使得爬完所有楼梯消耗的体力值之和最大，即 $\max_{p \in S} \sum_{i=l_j}^{r_j-1} |p_i-p_{i+1}|$，其中 $S$ 表示将 $\{h_{l_j}, h_{l_j+1}, \dots, h_{r_j}\}$ 重新排列能得到的序列的集合。但老 M 在忙着打 MMA，因此他想请你——M 氏混元形意太极拳的第 $992\,844\,853$ 个真传弟子，计算这个最大值。

输入格式

第一行两个正整数 $n, m$，分别表示平台的个数与仰慕者总数。

第二行 $n$ 个正整数 $h_1\sim h_n$，依次表示平台 $1\sim n$ 的高度。

接下来 $m$ 行，第 $i$ 行两个正整数 $l_i, r_i$（$1 \le l_i < r_i \le n$），表示有新的仰慕者来拜师学艺，你需要回答区间 $[1_i,r_i]$ 经过重排列后，耗费的最大体力值。

输出格式

$m$ 行，第 $i$ 行一个整数，表示第 $i$ 位仰慕者花费的最大体力值。

样例数据

样例输入

4 4
3 2 2 4
1 3
1 4
2 4
2 3

样例输出

2
5
4
0

样例解释

第一次询问，一种最优的方案为 $[2,3,2]$，耗费体力值为 $2$。

第二次询问，一种最优的方案为 $[3,2,4,2]$，耗费体力值为 $5$。

第三次询问，一种最优的方案为 $[2,4,2]$，耗费体力值为 $4$。

第四次询问，一种最优的方案为 $[2,2]$，耗费体力值为 $0$。

数据范围

子任务 1（$5\%$）：$n, m \le 10$；

子任务 2（$10\%$）：$h_i \le 2$；

子任务 3（$20\%$）：$h_i \le 3$；

子任务 4（$25\%$）：$n, m \le 2000$；

子任务 5（$40\%$）：无附加限制。

对于所有数据，有 $2 \le n, m \le 200\,000$，$1 \le h_i \le 10^9$。

保证对于所有询问，满足 $1 \le l_i < r_i \le n$。