D - Range Mod Query
Darjeeling
3
s
1024
MB
500
点
問題文
長さ $N$ の正整数列 $A_1,A_2, \cdots ,A_N$ があります。
以下のクエリが $Q$ 個来るので、全て処理してください。
$i \space (1 \leq i \leq Q)$ 番目のクエリでは整数 $l_i, r_i \space (1 \leq l_i < r_i \leq N)$ が与えられます。
$(...((A_{l_i} \bmod A_{l_i + 1}) \bmod A_{l_i + 2}) ... )\bmod A_{r_i}$ を計算してください。
なお、非負整数 $X$、正整数 $Y$ に対して $(X \bmod Y)$ とは、$X$ を $Y$ で割った余り のことを表します。
制約
- 入力は全て整数
- $2 \leq N \leq 1.5 \times 10^5$
- $1 \leq Q \leq 1.5 \times 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq l_i < r_i \leq N$
入力
$N$
$A_1 \space A_2 \space \ldots \space A_N$
$Q$
$l_1 \space r_1$
$l_2 \space r_2$
$\vdots$
$l_Q \space r_Q$
出力
$Q$ 行出力してください。
$i \space (1 \leq i \leq Q)$ 行目には $i$ 番目のクエリの答えを出力してください。
入力例 1
5
5 3 4 1 2
3
1 3
2 4
4 5
出力例 1
2
0
1
1 番目のクエリの答えは $(5 \bmod 3) \bmod 4 = 2$ です。
2 番目のクエリの答えは $(3 \bmod 4) \bmod 1 = 0$ です。
3 番目のクエリの答えは $1 \bmod 2 = 1$ です。
入力例 2
2
2 1
1
1 2
出力例 2
0
入力例 3
10
199 949 462 317 760 581 66 892 48 151
3
2 7
7 9
1 3
出力例 3
25
18
199