【题目描述】

$小 Z 有一条被分成 𝑛 个格子的长带子，从左到右第 𝑖 个格子的高度为 𝑎_𝑖。

小 Z 会从左到右检查这条带子。对于相邻的两个格子 𝑖 和 𝑖+1：

•如果 𝑎_𝑖≤𝑎_𝑖+1，检查时不会产生损耗；

•如果 𝑎_𝑖>𝑎_𝑖+1，检查时会产生 𝑎_𝑖−𝑎_𝑖+1 的损耗。$

因此，一条带子的总损耗定义为：

$$∑_{𝑖=1}^{𝑛−1} max(0,𝑎_𝑖−𝑎_{𝑖+1})$$

现在小 Z 想尝试一些折带方案。每次他会选择一个区间 $[𝑙,𝑟]$，把这一段带子左右翻 转后放回原处。

也就是说，原序列 $a_1,𝑎_2,⋯,𝑎_{𝑙−1},𝑎_𝑙,𝑎_{𝑙+1},⋯,𝑎_𝑟,𝑎_{𝑟+1},⋯,𝑎_𝑛$

会变成 $a_1,𝑎_2,⋯,𝑎_{𝑙−1},𝑎_𝑟,𝑎_{𝑟−1},⋯,𝑎_𝑙,𝑎_{𝑟+1},⋯,𝑎_𝑛$

每次询问互相独立。也就是说，一次询问结束后，带子会恢复到最初的状态。

请你对每次询问，求出折带后的总损耗。

【输入格式】

第一行包含两个正整数$𝑛,𝑞$，分别表示带子的格子数和询问次数。

第二行包含 𝑛 个正整数 $𝑎_1,𝑎_2,⋯,𝑎_𝑛，$表示每个格子的高度。

接下来$𝑞$ 行，每行包含两个正整数 $𝑙,𝑟，$表示一次折带询问。

【输出格式】

输出 𝑞 行，每行一个整数，表示对应询问中折带后的总损耗。

7 5
4 1 3 2 6 2 5
2 5
1 4
4 4
3 7
1 7

6
6
8
10
9

【样例1解释】

初始带子的总损耗为：

(4−1)+(3−2)+(6−2)=8

对于第一次询问，翻转区间 [2,5] 后，序列变为：

1 4 6 2 3 1 2 5

此时总损耗为：

(6−2)+(3−1)=6

对于第三次询问，翻转区间 [4,4]，带子没有发生变化，因此答案仍为 8。

【数据范围】

对于所有测试数据，保证 $1≤𝑛,𝑞≤5×10^5，1≤𝑎_𝑖≤10^9，1≤𝑙≤𝑟≤𝑛。$