P5501 [LnOI2019] 来者不拒，去者不追

题目提供者：朝田诗乃 

给定一个长度为$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$$

无

无

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