Given N non negative numbers, the task is to answer M queries.

Each query is as follows: 

Given u,v you need to find the pairwise product sum (u and v are zero indexed)

a_ua_u + a_u+1a_u+1 + a_u+1a_u + a_u+2a_u+2 + a_u+2a_u+1 + a_u+2a_u + ... + a_va_v + a_va_v-1 + ... + a_va_u

Input

N
a0 a1 ... aN-1
M
u1 v1
u2 v2
...
uM vM

Output

Print the answer for each query in a separate line.

Example

Input:
5
2 0 1 3 3
3
0 2
1 2
3 4

Output:
7
1
27

Constraints

0 <= u <= v < N
N <= 100000
M <= 100000
0 <= a_i <= 1000000