思考题 that is easier than #14

Sort and Sort and Sort and Sort

You are given an integer array A of length N. And you are given Q queries. For each query, you are given Li and Ri.
You need to find out the sum of products of adjcent numbers in the sorted array A[Li,Ri]

Example

A={1,2,3,4,5}
Q={[1,3],[2,4],[1,5]}
Output
8
18
40
Explain
1\times2+2\times3=8
2\times3+3\times4=18
1\times2+2\times3+3\times4+4\times5=40

Constriants

Subtask 1(50%): The array is sorted
Subtask 2(50%): Nothing
N<=100000,Ai<=1e9

Solution

See Ep.14