小慕拿到了一个数组a，她用这个数组构造一个新数组b，其中ai表示b数组中有ai个i。 例如，若a = [2, 3, 1]，那么b = [1, 1, 2, 2, 2, 3]，因为a1=2，代表b数组中有2个1；a2=3，代表b数组中有3个2；a3=1，代表b数组中有1个3。 现在给定a数组，你需要帮小慕求出b数组中所有的之和。 由于答案可能过大，请对10^9+7。 数组的极差指最大值减去最小值。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行输入一个正整数n，代表a数组的元素数量。 第二行输入n 个正整数ai，代表a数组的元素。 1 ≤ n ≤ 10^5 1 ≤ ai ≤ 10^9
输出描述
一个整数，代表数组中所有区间的极差之和，对10^9+7取模的值。
示例
示例 1
输入
2 2 1
输出
2
时间限制 1000 ms · 内存限制 128 MB