题解：贡献法计数+前缀和

考虑第$i$个元素对结果的贡献，选择第$i$个元素对结果的贡献 $b[i]*(b[i+1]*1+b[i+2]*2+...+b[k]*(k-i))$

如果是选择第$i+1$个元素，对结果的贡献为$b[i+1]*(b[i+2]*1+b[i+3]*2+...+b[k]*(k-i-1))$

右边的差值其实就是$b[i+1]+b[i+2]+...+b[k]$

因此可以预处理一个后缀和数组来去一遍遍历，一遍计算，当然，也可以不使用后缀和数组，维护两个变量即可

题目描述

米小游有一天拿到了一个数组$a$，他用这个数组构造一个新数组$b$，其中$a_i$代表$b$数组中有$a_i$个$i$。例如，若$a=[2,3,1]$，那么$b=[1,1,2,2,2,3]$。 现在给定$a$数组，你需要帮米小游求出$b$数组中所有连续子数组的极差之和。由于答案可能过大，请对$10^9+7$取模。数组的极差指最大值减去最小值。

输入格式

第一行输入一个正整数$n$，代表$a$数组的元素数量

第二行输入$n$个正整数$a_i$，代表$a$数组的元素。

$1\le n\le 10^5$

$1 \le a_i\le 10^6$

输出格式

一个整数，代表数组中所有区间的极差之和，对$10^9+7$取模的值。

样例

输入

2
2 1

输出

2

说明

a=[2,1]时，b数组为[1,1,2]。

此时b数组共有6个连续子数组:

[1]的极差为0

[1]的极差为0

[2]的极差为0

[1,1]的极差为0

[1,2]的极差为1

[1,1,2]的极差为1

因此答案是0+0+0+0+1+1=2