题目描述

塔子哥有一天拿到了一个数组$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