問題文

石油王となったすぬけ君はガソリンをこよなく愛していて、王国内の移動には車を欠かさず使う。
王国には$N$個のガソリンスタンドがあり、$i$ 個目のガソリンスタンドではガソリンが $1$ Lあたり $V_i$ 円で売っている。

また、ガソリンスタンドは $1$ 番目から $N$ 番目まで一直線上に並んでおり、$i$ 個目と$j$ 個目のガソリンスタンドを移動するのには$|i-j|$ Lのガソリンが必要である。

さて、すぬけ君は $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$ 個与えられ、$i$ 番目の整数として、 $i$ 番目のガソリンスタンドでの $1$ Lあたりのガソリンの値段 $V_{i}(1≦V_{i}≦100,000)$ が与えられる。
• 続く $Q$ 行のうちの $i$ 行目には $i(1≦i≦Q)$ 日目にすぬけ君がスタートするガソリンスタンド $S_{i}(1≦S_{i}≦N)$ とゴールであるガソリンスタンド $T_{i}(1≦T_{i}≦N)$ が空白区切りで与えられる。このとき、$S_{i}≠T_{i}$ であることが保障されている。

配点

この問題には部分点はない。

出力

$i(1≦i≦Q)$ 行目に $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

遠回りをしていく方がよい場合もあることに注意せよ。