D. Sums of Segmentstime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given a sequence of integers $$$[a_1, a_2, \dots, a_n]$$$. Let $$$s(l,r)$$$ be the sum of elements from $$$a_l$$$ to $$$a_r$$$ (i. e. $$$s(l,r) = \sum\limits_{i=l}^{r} a_i$$$).Let's construct another sequence $$$b$$$ of size $$$\frac{n(n+1)}{2}$$$ as follows: $$$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)]$$$.For example, if $$$a = [1, 2, 5, 10]$$$, then $$$b = [1, 3, 8, 18, 2, 7, 17, 5, 15, 10]$$$.You are given $$$q$$$ queries. During the $$$i$$$-th query, you are given two integers $$$l_i$$$ and $$$r_i$$$, and you have to calculate $$$\sum \limits_{j=l_i}^{r_i} b_j$$$.InputThe first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10 \le a_i \le 10$$$).The third line contains one integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$).Then $$$q$$$ lines follow, the $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le \frac{n(n+1)}{2}$$$).OutputPrint $$$q$$$ integers, the $$$i$$$-th of which should be equal to $$$\sum \limits_{j=l_i}^{r_i} b_j$$$.ExampleInput41 2 5 10151 11 21 31 41 51 105 106 102 83 43 103 85 65 51 8Output1
4
12
30
32
86
56
54
60
26
82
57
9
2
61