D. Суммы на отрезках
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность целых чисел $$$[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$$$.

Пример
Входные данные
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
4
12
30
32
86
56
54
60
26
82
57
9
2
61