当前没有测试数据。

问题重述

牛妹正在玩多米诺骨牌。她将 $n$ 张多米诺骨牌从左到右排成一排，每一张多米诺骨牌都有重量，第 $i$ 张多米诺骨牌的重量记为 $a_i$。随后，牛妹定义了新的游戏规则，初始时她会选定 $l, r$（$1 \leq l \leq r \leq n$），一轮游戏过程如下：

• 手动选择第 $l$ 张多米诺骨牌，将其向右推倒；
• 对于第 $l+1$ 张多米诺骨牌，若满足 $a_l \geq a_{l+1}$，则其也会向右倒下；
• 对于第 $l+2$ 张多米诺骨牌，若满足 $a_l + a_{l+1} \geq a_{l+2}$，则其也会向右倒下；
• ……；
• 对于第 $i$ 张多米诺骨牌，若其左侧的第 $i-1$ 张多米诺骨牌倒下，且第 $i$ 张多米诺骨牌的重量不大于其左侧倒下的全部多米诺骨牌的重量之和，则其也向右倒下，即当 $\sum_{k=l}^{i-1} a_k \geq a_i$ 时，其向右倒下；
• 对于第 $r$ 张多米诺骨牌，如果其倒下了，那么这一局游戏就是完美的。

牛可乐希望牛妹选择的每一对 $l, r$ 都能使得这一局游戏是完美的。为此，在牛妹选定 $l, r$ 后，牛可乐会调整多米诺骨牌的重量。具体地，每一次调整他会选择一块多米诺骨牌，然后将其重量增加 $1$ 或者减少 $1$。

你需要帮助牛可乐计算，对于每一对 $l, r$，牛可乐至少需要调整多少次多米诺骨牌的重量，才能使得这一局游戏是完美的。调整仅针对当前轮游戏，在每一轮游戏结束后骨牌的重量都会恢复。

输入格式

• 第一行输入两个整数 $n, q$（$1 \leq n, q \leq 2 \times 10^5$），代表多米诺骨牌的个数和询问次数。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示多米诺骨牌的重量。
• 此后输入 $q$ 行，每行输入两个整数 $l, r$（$1 \leq l \leq r \leq n$）代表一次询问。

输出格式

对于每一次询问，新起一行。输出一个整数，代表牛可乐最少需要调整的次数。每一次询问相互独立。

示例

示例 1：

输入：

4 2
2 1 2 7
2 3
1 4

输出：

1
2

说明：

• 对于第一次询问，其中一种最优的调整方案是：将第 $3$ 张多米诺骨牌的重量减少 $1$。
• 对于第二次询问，其中一种最优的调整方案是：将第 $3$ 张多米诺骨牌的重量增加 $1$、将第 $4$ 张多米诺骨牌的重量减少 $1$，此时，各张多米诺骨牌的重量分别为 $2, 1, 3, 6$，符合题意，游戏完美。

示例 2：

输入：

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

输出：

0
2
3
2