Description

Given a sequence $a$ of length $n$. There are $m$ queries. For each query, you need to find the sum of the “Abbi value” of all numbers in the interval $[l,r]$.

The Abbi value is defined as follows: if $a_i$ is the $k$-th smallest in the query interval $[l,r]$, then its “Abbi value” equals $k \times a_i$.

To avoid ambiguity, here is an example:

Given the sequence $\{1,2,2,3\}$, then $1$ is the $1$-st smallest, $2$ is the $2$-nd smallest, and $3$ is the $4$-th smallest. The sum of Abbi values of the sequence is:

Input Format

The first line contains two integers, $n$ and $m$, representing the length of the sequence and the number of queries.

The second line contains $n$ numbers. The $i$-th number is $a_i$, representing the initial value of the sequence.

The next $m$ lines each contain two numbers $l$ and $r$, representing a query interval.

Output Format

For each query, output one line with the answer.

4 2
1 2 2 3
1 4
1 2

21
5

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

51
49
11
7
2

Hint

Constraints

For the first 2 test points, $1 \le n,m \le 1000$, time limit $1\text{s}$.

For the next 14 test points, $1 \le n,a_i,m \le 100000$, $1 \le l \le r \le n$, time limit $1\text{s}$.

For the last 2 test points, $1 \le a_i \le 100000$, $1 \le l \le r \le n$, $1 \le n,m \le 500000$, time limit $3\text{s}$.

It is recommended to use fast input. It is recommended to enable $O2$ optimization.

The testdata has been strengthened.

Translated by ChatGPT 5