You 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). The 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})). Print (q) integers, the (i)-th of which should be equal to (\sum \limits_{j=l_i}^{r_i} b_j).