总力量定义为以下两个值的 乘积：
巫师中最弱的能力值
组中所有巫师的个人力量值之和
1. 单调栈+前缀和+前缀和
根据单调栈求得每一个值的辖域（当前值为最小值的最长数组范围）
接下来问题就转化成了求在辖域中包含当前值所有子数组的和
求和我们采用前缀和的方式
对于abcde，假设c为当前辖域最小值，则所有子数组和为presum[c/d/e]-presum[a/b/c-1]
presum[c/d/e]要分别列举三次求和，由左边个数决定，presum[a/b/c-1]要列举3次求和，由右边个数决定
为了快速求c/d/e的和，以及a/b/c的和，这里再次使用前缀和
class Solution {
public:
int totalStrength(vector<int>& arr) {
const int mod = 1e9+7;
int n = arr.size();
vector<int> monoStack; //单调栈
vector<int> left(n), right(n);//左右边界
for (int i = 0; i < n; i++) {//从左往右找左边更小值
while (!monoStack.empty() && arr[i] <= arr[monoStack.back()]) {//把更大的值挤出来，相等的视为更大，区间计算的时候不影响
monoStack.pop_back();
}
left[i] = monoStack.empty() ? -1: monoStack.back(); //左边界，左开
monoStack.emplace_back(i);//放入坐标
}
monoStack.clear();
for (int i = n - 1; i >= 0; i--) { //从右往左找右边更小值
while (!monoStack.empty() && arr[i] < arr[monoStack.back()]) {
monoStack.pop_back();
}
right[i] = monoStack.empty() ? n : monoStack.back(); //右边界，右开
monoStack.emplace_back(i);
}
vector<long long> presum(n+1);
vector<long long> sumsum(n+2);
for(int i=0;i<n;i++){
presum[i+1] = presum[i]+arr[i];//前缀和
sumsum[i+2] = (sumsum[i+1]+presum[i+1])%mod;
}
long long res = 0;
for(int i=0;i<n;i++){//遍历每一个数
int r = right[i]-1;//这里是闭区间
int l = left[i]+1;//这里是闭区间
//presum[i]/presum[i+1]....presum[r] - presum[i-1]....presum[l]
//左边个数为i-l+1,右边个数为r-i+1(包含本身)
long long cur = ((sumsum[r+2]-sumsum[i+1])*(i-l+1) - (sumsum[i+1]-sumsum[l])*(r-i+1))%mod;
res = (res+cur*arr[i])%mod;
}
return (res+mod)%mod;
}
};