给定一个长度为 n的序列 a。给定 m个询问，每次询问一个区间中 [l,r]中所有数的“Abbi值”之和
Abbi值定义为：若 ai在询问区间 [l,r]中是第 k小，那么它的“Abbi值”等于 k×ai。
为了消除歧义举个例子：
有序列1 2 2 3，那么1是第1小，2是第2小，3是第4小，序列Abbi值和为
1×1+2×2+2×2+3×4=21

第一行两个整数，n和 m，分别表示序列长度和询问组数。
第二行 n个数，第 i个数为 ai，表示序列的初始值。
接下来 m行，每行两个数 l和 r，表示询问区间。

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

样例二：
输入：
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,ai,m≤100000， 1≤l≤r≤n，时限1s。
最后两个数据点， 1≤ai≤100000， 1≤l≤r≤n， 1≤n,m≤500000，时限3s。
建议使用读入优化。

莫队 数据结构 线段树 树状数组