思考题 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

Constriants

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

Solution

See Ep.14