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$.

Input

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}$).

Output

Print $q$ integers, the $i$-th of which should be equal to $\sum \limits_{j=l_i}^{r_i} b_j$.

见题面 Input 部分

见题面 Output 部分