Дана последовательность целых чисел $$$[a_1, a_2, \dots, a_n]$$$. Обозначим $$$s(l,r)$$$ как сумму элементов от $$$a_l$$$ до $$$a_r$$$ (т. е. $$$s(l,r) = \sum\limits_{i=l}^{r} a_i$$$).
Построим другую последовательность $$$b$$$ размером $$$\frac{n(n+1)}{2}$$$ следующим образом: $$$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$$$.
41 2 5 10151 11 21 31 41 51 105 106 102 83 43 103 85 65 51 8
1 4 12 30 32 86 56 54 60 26 82 57 9 2 61
Название |
---|