题目背景

题目提供者：朝田诗乃

题目描述

给定一个长度为 $n$ 的序列 $a$。给定 $m$ 个询问，每次询问一个区间中 $[l,r]$ 中所有数的“Abbi 值”之和。

Abbi 值定义为：若 $a_i$ 在询问区间 $[l,r]$ 中是第 $k$ 小，那么它的“Abbi 值”等于 $k \times a_i$。

为了消除歧义举个例子：

有序列 $\{1,2,2,3\}$，那么 $1$ 是第 $1$ 小，$2$ 是第 $2$ 小，$3$ 是第 $4$ 小，序列 Abbi 值和为：

输入格式

第一行两个整数，$n$ 和 $m$，分别表示序列长度和询问组数。

第二行 $n$ 个数，第 $i$ 个数为 $a_i$，表示序列的初始值。

接下来 $m$ 行，每行两个数 $l$ 和 $r$，表示询问区间。

输出格式

对于每个询问，输出一行表示答案。

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

提示

前 2 个数据点，$1≤n,m≤1000$，时限 1s。

接下来 14 个数据点，$1≤n,a_i,m≤100000$，$1≤l≤r≤n$，时限 1s。

最后两个数据点，$1≤a_i≤100000$，$1≤l≤r≤n$，$1≤n,m≤500000$，时限 3s。

建议使用读入优化。建议开启 O2 优化。

数据已经过加强。