给你一个整数序列$$$[a_1, a_2, \dots, a_n]$$$。令 $$$s(l,r)$$$ 为从 $$$a_l$$$ 到 $$$a_r$$$ 的元素之和(即 $$$s(l,r) = \sum\limits_{i=l}^{r} a_i$$$)。
让我们构建另一个大小为 $$$\frac{n(n+1)}{2}$$$ 的序列 $$$b$$$,如下所示: $$$b = [s(1,1), s(1,2), \dots, s(1,n), s(2,2), s(2,3), \dots, s(2,n), s(3,3), \dots, s(n,n)]$$$。
例如,如果 $$$a = [1, 2, 5, 10]$$$,则 $$$b = [1, 3, 8, 18, 2, 7, 17, 5, 15, 10]$$$。
您收到 $$$q$$$ 查询。在第 $$$i$$$ 次查询期间,您将获得两个整数 $$$l_i$$$ 和 $$$r_i$$$,并且您必须计算 $$$\sum \limits_{j=l_i}^{r_i} b_j$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10 \le a_i \le 10$$$)。
第三行包含一个整数$$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$)。
接下来是 $$$q$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le \frac{n(n+1)}{2}$$$)。
输出
打印 $$$q$$$ 整数,其中第 $$$i$$$ 应等于 $$$\sum \limits_{j=l_i}^{r_i} b_j$$$。
示例
输入 #1
4 1 2 5 10 15 1 1 1 2 1 3 1 4 1 5 1 10 5 10 6 10 2 8 3 4 3 10 3 8 5 6 5 5 1 8
输出 #1
1 4 12 30 32 86 56 54 60 26 82 57 9 2 61