All Submissions


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


0> 1> ... N-1>

1> 1>
2> 2>
...
M> M>
 

Output

Print the answer for each query in a seperate line.

Sample Input


5
2 0 1 3 3
3
0 2
1 2
3 4


Sample Output


7
1
27


Constraints

  • u>=0, u
  • v>=0, v
  • u<=v
  • N<=100000
  • M<=100000
  • 0 <= ai <= 10000


Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0