[LnOI2019]来者不拒,去者不追

题目背景

题目提供者:朝田诗乃 ![avartar](https://cdn.luogu.com.cn/upload/pic/66100.png)

题目描述

给定一个长度为$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值和为 $$1 \times 1+2 \times 2+2 \times 2+3 \times 4=21$$

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

4 2
1 2 2 3
1 4
1 2

输出样例 #1

21
5

输入样例 #2

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

输出样例 #2

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优化。 数据已经过加强。