Description

You are given a integer sequence (a₁, a₂, ..., a_n) of length n.

In this problem, you need to answer q quiries, each query is of the form:

• l r

Meaning you need to answer the sum of a_l * 1 + a_l+1 * 2 + a_l+2 * 3 + ... + a_r-1 * (r - l) + a_r * (r - l + 1).

 

Contraints

• 1 <= n <= 10⁵
• 0 <= a_i < 2³², i = 1, 2, ..., n
• All a_i s are integer
• For each query, 1 <= l <= r <= n

Subtask

• Testcase 1~3: n <= 1000
• Testcase 4~6: No additional constraints

Input

The first line contains an integer n: the length of the sequence.

The second line contains n integers a₁, a₂, ..., a_n, each integer is seperated by a blank.

The third line contains an integer q: the number of queries you need to answer.

For the next q line, each line contains two integer l r, seperated by a blank.

Output

For each query, print the answer in one line.

 

Hint

For the first query in the sample input, the answer should be a₁ * 1 + a₂ * 2 + a₃ * 3 = 1 * 1 + 1 * 2 + 4 * 3 = 15. For the second query, the answer should be a₅ * 1 + a₆ * 2 = 1 * 1 + 2 * 4 = 9.

Sample Input  Download

Sample Output  Download

Tags

Discuss