Problem Description

Given a sequence \(a\) of length \(n\). There are \(m\) queries, each asking for the sum of the "Abbi values" of all numbers in a specified interval \([l, r]\).

The "Abbi value" is defined as follows: if \(a_i\) is the \(k\)-th smallest number in the query interval \([l, r]\), then its "Abbi value" is \(k \times a_i\).

To clarify, consider the sequence 1 2 2 3. Here, 1 is the 1st smallest, 2 is the 2nd smallest, and 3 is the 4th smallest. The sum of the Abbi values for this sequence is:

\[1 \times 1 + 2 \times 2 + 2 \times 2 + 3 \times 4 = 21\]

Input Format

The first line contains two integers, \(n\) and \(m\), representing the length of the sequence and the number of queries, respectively.

The second line contains \(n\) integers, where the \(i\)-th integer is \(a_i\), representing the initial values of the sequence.

The next \(m\) lines each contain two integers \(l\) and \(r\), representing the query interval.

Output Format

For each query, output a single line containing the answer.

Sample Input and Output

Sample Input #1

4 2
1 2 2 3
1 4
1 2

Sample Output #1

21
5

Sample Input #2

10 5
8 6 9 8 1 1 3 10 7 9
5 8
1 3
5 7
9 9
5 6

Sample Output #2

51
49
11
7
2

Notes/Hints

For the first 2 data points, \(1 \leq n, m \leq 1000\), with a time limit of 1 second.

For the next 14 data points, \(1 \leq n, a_i, m \leq 100000\), \(1 \leq l \leq r \leq n\), with a time limit of 1 second.

For the last 2 data points, \(1 \leq a_i \leq 100000\), \(1 \leq l \leq r \leq n\), \(1 \leq n, m \leq 500000\), with a time limit of 3 seconds.

It is recommended to use input optimization and to enable O2 optimization.

The data has been strengthened.

见题面 Input 部分

见题面 Output 部分