Start: May, 03, 2023 16:00:00
20230503模拟赛二
End: May, 30, 2023 15:00:00
Time elapsed:
Time remaining:

CDR 的超市排队 1666

Time Limit:  1 Sec    Memory Limit:   256 MB
Submission:217     AC:12     Score:100


Description


CDR 在超市排队,队伍实在是太长了,总共有 $n$ 个人,但是她发现她可以根据每个人手里的东西来大致判断这个人需要花多少时间结账

于是为了打发时间,CDR 给自己出了一个问题

假设有 $3$ 个人,结账需要花费的时间分别为 $1,2,3$

每个人的排队时间是她的等待时间加上她自己结账的时间,所以这 3 个人的排队时间分别为 $1,3,6$

这三个人总的排队时间即为 $1+3+6=10$

计算所有人的排队总时间实在是太简单了

所以 CDR 想知道,如果单独选出其中第 $l$ 个人到第 $r$ 个人(包含这两个人),把她们移到一个新的窗口去结账,所有人总的等待时间是多少?

P.S. 这里不考虑其她任何时间花费,例如移动等时间花费,都不考虑

Input


输入第一行,包含一个正整数 $n$ ,表示排队的总人数

接下来一行,包含 $n$ 个正整数 $a_i$,表示每个人结账需要花费的时间

接下来一行,包含一个正整数 $q$ ,表示询问的次数。

接下来 $q$ 行,每行两个正整数 $l, r$ ,表示这一次的询问,含义如题。

对于 $30\%$ 的数据, $1 \leq n, q \leq 10 ^ 2, 1 \leq a_i \leq 10 ^ 3$ 。

对于 $60\%$ 的数据, $1 \leq n, q \leq 5 \times 10 ^ 3, 1 \leq a_i \leq 10 ^ 6$

对于 $100\%$ 的数据,$1 \leq n, q \leq 10 ^ 5, 1 \leq a_i \leq 10 ^ 9$


Output


对于每个询问输出一行,表示询问的结果,因为答案可能较大,所以请将答案对 $10^9+7$ 取模

Samples

input:
3 1 2 3 1 1 3
output:
10