PAIRSUM - Sum of Pairwise Products

no tags 

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)

auau + au+1au+1 + au+1au + au+2au+2 + au+2au+1 + au+2au + ... + avav + avav-1 + ... + avau

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 <= ai <= 1000000


hide comments
Pranjal Successena: 2013-03-07 16:34:04

can u give more test cases.
my program gives correct output according to the given test cases but still it's "wrong answer"

Pranjal Successena: 2013-03-07 16:34:01

can u give more test cases.
my program gives correct output according to the given test cases but still it's "wrong answer"

BOND: 2012-08-25 06:21:36

ohh man, i am really bad at type conversions... two WA's after AC :(

Kiran Danduprolu: 2011-10-05 22:07:36

Nice problem ... had fun solving it

:D: 2011-09-21 08:48:00

Unsigned long long should be enough to hold final and intermediate results.


Added by:Manukranth
Date:2011-09-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64