問題文

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

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

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

制約

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

  • 2N1052 \leq N \leq 10^5
  • 1T5×1041 \leq T \leq 5×10^4
  • 1Ai1091 \leq A_i\leq 10^9 (1iN)(1\leq i \leq N)
  • 1Xi<YiN1 \leq X_i < Y_i \leq N (1iT)(1\leq i \leq T)

入力

NN TT
A1A_1 A2A_2 ...... ANA_N
X1X_1 Y1Y_1
X2X_2 Y2Y_2
......
XTX_T YTY_T

出力

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

サンプル

入力1
5 4
2 4 8 12 7
1 3
3 4
4 5
2 5
出力1
4
2
1
2

11 つ目のクエリについて、1133 番目の歯車は以下のようになっています。
図
11 つ目の歯車を44回転させることで、22 つ目の歯車がちょうど 22 回転します。
22 つ目の歯車が22回転することで、33 つ目の歯車がちょうど 11 回転します。
よって、33 つ目の歯車を 11 回転させるためには、 44 回転が最小です。

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

Submit


Go (1.21)