该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

完成符文考验后，你来到第三赛场——魔法小镇的传奇酒馆。

酒馆大厅内整齐排列着 $n$ 个酒桶（编号 $1$ 到 $n$），每个酒桶底面积为 $1$，能无限装酒。相邻酒桶 $i$ 和 $i+1$ 通过一根魔法溢酒管相连，这根溢酒管的高度为 $h_i$。保证 $h_i$ 互不相同。

老板将进行 $q$ 次独立实验：

• 每次实验，所有酒桶初始为空；
• 选择一个酒桶 $a$ 不断倒入魔法酒。问：最少需要倒入多少酒，才能让酒第一次出现在另一个酒桶 $b$ 中？

溢酒规则：

• 当某根溢酒管两边的酒面高度 $<h_i$ 时，它们之间不会有任何酒流动。
• 如果某一侧酒面高度先达到 $h_i$，那么这一侧的酒面就会停留在高度 $h_i$。继续倒入的酒将全部通过该管流向另一侧，直到另一侧的酒面也升到 $h_i$。
• 一旦某根溢酒管两边的酒面都到达或超过高度 $h_i$，这两只酒桶就会被完全连通，之后它们的酒面始终保持相同，并随继续注入的酒共同升高。

（注：溢酒管足够细，所以可以认为溢酒管中不会有酒残留。所有酒桶足够高，永远不会装满。）

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示酒桶数量和实验次数。

第二行包含 $n-1$ 个整数 $h_1,h_2,\dots,h_{n-1}$，表示相邻酒桶之间溢酒管的高度。

接下来 $q$ 行，每行两个整数 $a_i,b_i$，表示第 $i$ 次实验从酒桶 $a_i$ 倒入魔法酒，观察最少需要倒入多少酒，才能让酒第一次出现在另一个酒桶 $b_i$ 中。

输出格式

输出 $q$ 行，每行一个整数，表示对应实验所需倒入的最少酒量。

样例

样例 $1$ 输入

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

样例 $1$ 输出

25
18
14
12

样例 $1$ 解释

样例$1$图示

数据范围与提示

对于所有测试点，满足 $2\le n\le 5\times 10^{5}$，$1\le q\le 5\times 10^{5}$，$1\le h_i\le 10^{9}$，$h_i$ 互不相同，$1\le a_i\le n$，$1\le b_i\le n$，且 $a_i\ne b_i$。

子任务