AT_ijpc2015_f.ガソリンスタンド

すぬけ君已经成为了一名石油大亨，对汽油的热爱无可比拟，他在王国内的出行总是少不了汽车。王国中有 $N$ 个加油站，第 $i$ 个加油站的汽油价格是每升 $V_i$ 日元。

这些加油站从 $1$ 到 $N$ 依次排列在一条直线上，要从第 $i$ 个加油站移动到第 $j$ 个加油站，需要消耗 $|i-j|$ 升的汽油。

すぬけ君计划了 $Q$ 天的加油站旅行。在每一天的行程中，他从第 $S_i$ 个加油站出发，前往第 $T_i$ 个加油站。他可能会途经一些加油站，每到一个加油站，哪怕是目的地，他都需要给汽车加满油。途径的加油站可选择是否停留加油。

作为すぬけ君的司机，すめけ不能影响加油站的选择，他需要计算出每次旅行时，在哪些加油站停留可以花费最少。

你的任务是帮助すめけ确定每一天的行程所需的最低油费。

需要注意的是，每天旅行开始之前，汽车的油箱都是满的，不会因为在任意两个加油站之间的移动而缺油。

输入以如下格式给出：

$N \ Q \ V_1 \ V_2 \ \ldots \ V_N \ S_1 \ T_1 \ S_2 \ T_2 \ \ldots \ S_Q \ T_Q$

• 第一行包含两个整数 $N(1 \leq N \leq 4000)$ 和 $Q(1 \leq Q \leq 200,000)$，分别表示加油站的数量和旅行的天数。
• 第二行包含 $N$ 个整数，第 $i$ 个整数表示第 $i$ 个加油站的每升汽油价格 $V_i(1 \leq V_i \leq 100,000)$。
• 接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $S_i(1 \leq S_i \leq N)$ 和 $T_i(1 \leq T_i \leq N)$，指定第 $i$ 天的出发点和目的地，并确保 $S_i \neq T_i$。

对于每一天的旅行，输出一行表示该次行程的最低花费。

本翻译由 AI 自动生成