给你一个长度为n的序列,定义一个区间[l,r]的价值为: (r-l+1)×min(al,al+1, …. ,ar-1,ar)×max(a1,al+1, …. ,ar-1,ar) 求该序列的每一个子区间价值之和。 答案对 109取模。

为了计算给定序列的每个子区间的价值之和，我们可以使用两个指针法（滑动窗口）来迭代地处理每个区间。对于每个区间 `[l, r]`，我们需要找到 `min(a_l, a_{l+1}, ..., a_r)` 和 `max(a_1, a_{l+1}, ..., a_r)`，然后计算区间值 `(r - l + 1) * min * max`。

首先，我们初始化两个指针 `left` 和 `right` 分别指向序列的开始和结束，同时初始化最小值 `min_val` 和最大值 `max_val` 为序列的第一个元素。然后我们将左指针右移，更新最小值和最大值，直到左指针超过右指针。在这个过程中，每次移动右指针时，我们都检查新加入的元素是否影响最小值或最大值，并相应地更新这两个变量。同时，累加当前区间的值到结果上。

这是一个可能的 C++ 实现：

#include <vector>
using namespace std;

int calculateSum(vector<int>& nums, int n) {
    int left = 0;
    int right = 0;
    long long res = 0;
    int min_val = nums[0];
    int max_val = nums[0];

    while (left < right) {
        if (nums[right] <= min_val) {
            min_val = nums[right];
            res += (right - left) * min_val;
        } else if (nums[left] >= max_val) {
            max_val = nums[left];
            res += (right - left) * max_val;
        }
        
        // 移动右指针，保持当前区间不变
        right++;
        
        // 更新最大值和最小值
        if (right < n && nums[right] < min_val)
            min_val = nums[right];
        if (right < n && nums[left] > max_val)
            max_val = nums[left];
        
        // 左指针向右移动
        left++;
    }

    return res % 1e9;  // 返回结果并对1e9取模
}