问题描述

酥鱼变成了石油大亨，他非常热爱汽油，王国内的移动都离不开车。
王国里有$N$个加油站，第$i$个加油站的汽油价格为每升$V_i$元。

此外，加油站沿着直线从第1个到第$N$个排列，要从第$i$个加油站到第$j$个加油站需要消耗$|i-j|$升汽油。

现在，酥鱼计划在$Q$天内绕访加油站。

第$i$天，他打算去第$S_i$个加油站到第$T_i$个加油站。为了实现这个目标，酥鱼可能会经过一些其他加油站，但是每到一个加油站，不管这个加油站是否是目的地，他都会付钱让司机给车加满油。另外，他必须停下来到达目的地，但是在中途的路径上的加油站不一定要停，酥鱼可以自由选择要停在哪些加油站。

酥鱼的司机小可是不能阻止酥鱼加油的，因此他想知道酥鱼应该停在哪个加油站，才能以最低的费用从一个加油站到另一个加油站。

现在轮到你了。请计算出每个行程中，酥鱼要花费的最少金额。

注意，每天旅行之前，车里的油已经加满了，而且酥鱼的车不会在任何加油站没有油的情况下。

输入

输入从标准输入中按以下格式给出。

$N$ $Q$

$V_1$ $V_2$ ... $V_N$

$S_1$ $T_1$

$S_2$ $T_2$

...

$S_Q$ $T_Q$

• 第一行包含两个整数，加油站的数量$N(1≦N≦4000)$和酥鱼的旅行天数$Q(1≦Q≦200,000)$。
• 接下来的一行包含$N$个整数，用空格分隔，表示每个加油站的每升汽油价格$V_i(1≦V_i≦100,000)$。
• 接下来的$Q$行中，第$i$行（$1≦i≦Q$）包含两个整数，表示酥鱼在第$i$天出发的加油站$S_i(1≦S_i≦N)$和目的地加油站$T_i(1≦T_i≦N)$。保证$S_i≠T_i$。

输出

对于每个行程，输出酥鱼在该天行驶所需的最低费用。

输入示例1

3 3
5 3 4
3 1
1 2
2 1

输出示例1

8
3
5

输入示例2

5 5
9 5 10 6 6
5 1
2 1
2 3
1 4
1 4

输出示例2

24
9
10
17
17

输入示例3

6 1
100 100 100 5 3 1
1 4

输出示例3

13

注意考虑有时绕道可能会更好。