Abbi Value Sum Query

You are given a sequence \(a\) of length \(n\). You are then given \(m\) queries. In each query you are asked to compute the sum of the "Abbi values" of all numbers in the interval \([l, r]\).

The Abbi value for an element \(a_i\) in the query interval \([l,r]\) is defined as follows: Let the rank of \(a_i\) be \(k = (\#\{x \in [l,r] : x < a_i\}) + 1\). Then the Abbi value of \(a_i\) is \(k \times a_i\). In other words, every element \(a_i\) contributes \(a_i \times ((\mbox{the number of elements strictly less than }a_i\mbox{ in }[l,r]) + 1)\) to the sum.

For example, consider the sequence [1, 2, 2, 3]. In the sorted order of the interval, note that:

• The number 1 has 0 elements less than itself, so its rank is \(0+1=1\). Its contribution is \(1 \times 1 = 1\).
• Both occurrences of 2 have 1 element (the 1) strictly less than them, so their rank is \(1+1=2\). Each contributes \(2 \times 2 = 4\).
• The number 3 has 3 elements less than it (1 and the two 2's), so its rank is \(3+1=4\). Its contribution is \(3 \times 4 = 12\).

The overall sum is \(1+4+4+12=21\>.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the length of the sequence and \(m\) is the number of queries. The second line contains \(n\) integers representing the sequence \(a\). The following \(m\) lines each contain two integers \(l\) and \(r\) (1-indexed), representing the query interval.

Example:

4 2
1 2 2 3
1 4
2 3

outputFormat

For each query, output the sum of the Abbi values for the numbers in the interval \([l,r]\) on a separate line.

Example Output:

21
4

sample

4 2
1 2 2 3
1 4
2 3

21
4