题目描述

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

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

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

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

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

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

所以 徐老师想知道，如果单独选出其中第 $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$

Samples

3
1 2 3
1 
1 3

10

Limitation

1s, 1024KiB for each test case.