题目描述

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

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

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

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

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

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

所以 bgy 想知道，如果单独选出其中第 $l$ 个人到第 $r$ 个人（包含这两个人)，把他们移到一个新的窗口去结账，这些人每个人的等待时间之和是多少？

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

输入格式

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

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

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

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

输出格式

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

数据范围

对于 $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$

样例输入

9
8 10 5 9 9 10 7 5 7
10
8 9
3 6
8 9
2 6
1 2
1 9
7 9
1 9
3 9
4 9

样例输出

17
75
17
125
26
364
38
364
212
177