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
nadstratosfer: 2017-08-06 10:52:03

Fast IO + O(1) query answers, still TLE in Python :(

Edit Dec'2017: Surprised to find this problem in my AC list. Perhaps the TL has been tweaked and solutions rejudged.

Last edit: 2017-12-31 03:37:44
kira28: 2016-12-17 12:24:42

Same code:-
Java - TLE
C - AC
:(

baadshah_: 2016-07-03 18:52:08

Use scanf and printf

hmp: 2016-05-22 10:14:08

to avoid TLE for cin/cout not only use ios_base::sync_with_stdio(false); but also tie cin/cout;

Last edit: 2016-05-30 03:57:57
deradler: 2016-05-20 22:19:45

gud ques, derived a general formula ((sum of nos in a range)^2 + sum of squares of numbers)/2.

Last edit: 2016-05-20 23:15:19
ayush sinha: 2016-02-11 10:09:01

recall 10 class maths

sarvesh_19: 2016-02-05 22:01:13

use scanf printf ,long long int,.O(n+m) possible with DP :)

Nikhil Sheoran: 2015-03-06 18:20:24

Even with O(M+N) requires fast i/o..

Sudarshan K: 2015-01-07 09:00:34

Problem setter. Please move this to Cube Cluster. Can't submit in C/C++. Says Language available only on Cube Cluster.

AAKASH TYAGI: 2014-07-10 17:29:30

50th problem on spoj :)

answer queries in constant time


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