問題文

$N$個の歯車があり、$i$ 番目の歯車の歯数は $A_i$ です。
$1\leq i < N$ を満たす $i$ について、$i$ 番目の歯車と $i+1$ 番目の歯車が嚙み合っています。
歯車が空回りすることはなく、歯 $1$ つ $1$ つを噛み合わせながら回ります。

$T$ 個のクエリが与えられます。$i$ $(1\leq i \leq T)$ 番目のクエリでは、以下の問いの答えてください。

• $Y_i$ 番目の歯車を$1$回以上 回転させるために、$X_i$ 番目の歯車を最低で何回転させれば良いか、"整数"で答えてください。

制約

入力はすべて整数である。

• $2 \leq N \leq 10^5$
• $1 \leq T \leq 5×10^4$
• $1 \leq A_i\leq 10^9$ $(1\leq i \leq N)$
• $1 \leq X_i < Y_i \leq N$ $(1\leq i \leq T)$

入力

$N$ $T$
$A_1$ $A_2$ $...$ $A_N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$...$
$X_T$ $Y_T$

出力

$i$ $(1\leq i \leq T)$ 番目のクエリの答えを$i$行目に整数で出力せよ。

サンプル

5 4
2 4 8 12 7
1 3
3 4
4 5
2 5

4
2
1
2

$1$ つ目のクエリについて、$1$ ～ $3$ 番目の歯車は以下のようになっています。

$1$ つ目の歯車を$4$回転させることで、$2$ つ目の歯車がちょうど $2$ 回転します。
$2$ つ目の歯車が$2$回転することで、$3$ つ目の歯車がちょうど $1$ 回転します。
よって、$3$ つ目の歯車を $1$ 回転させるためには、 $4$ 回転が最小です。

$2$ つ目のクエリについて、
$3$ つ目の歯車を $1$ 回転させるだけでは、$4$ つ目の歯車は $1$ 回転に満たないです。
$4$ つ目の歯車を $1$ 回以上、回転させるために必要な最小回転数(整数)として、$2$ 回転が答えになります。