rectangles

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 1000010;
const int mod = 1e9 + 7;

int v[MaxN], left1[MaxN], left2[MaxN], right1[MaxN], right2[MaxN];

int multiply(int a, int b, int c, int d) {
    return (1LL * ((1LL * a * b) % mod) * ((1LL * c * d) % mod)) % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //ifstream fin("rectangles.in");
    //ofstream fout("rectangles.out");
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        left1[i] = left2[i] = 0;
        right1[i] = right2[i] = n + 1;
    }

    stack<int> st1, st2, aux;
    for (int i = 1; i <= n; i++) {
        while (!st2.empty() && v[i] > v[st2.top()]) {
            right2[st2.top()] = i;
            st2.pop();
        }
        while (!st1.empty() && v[i] > v[st1.top()]) {
            right1[st1.top()] = i;
            aux.push(st1.top());
            st1.pop();
        }
        st1.push(i);
        for (; !aux.empty(); aux.pop())
            st2.push(aux.top());
    }

    for (; !st1.empty(); st1.pop());
    for (; !st2.empty(); st2.pop());

    for (int i = n; i >= 1; i--) {
        while (!st2.empty() && v[i] >= v[st2.top()]) {
            left2[st2.top()] = i;
            st2.pop();
        }
        while (!st1.empty() && v[i] >= v[st1.top()]) {
            left1[st1.top()] = i;
            aux.push(st1.top());
            st1.pop();
        }
        st1.push(i);
        for (; !aux.empty(); aux.pop())
            st2.push(aux.top());
    }

    long long sol = 0;
    for (int i = 1; i <= n; i++) {
        if (left1[i] > 0) {
            int a = left1[i] - left2[i];
            int b = right1[i] - i;
            sol = (sol + multiply(a, b, v[i], v[left1[i]])) % mod;
        }
        if (right1[i] < n + 1) {
            int a = i - left1[i];
            int b = right2[i] - right1[i];
            sol = (sol + multiply(a, b, v[i], v[right1[i]])) % mod;
        }
    }

    cout << sol << "\n";
    return 0;
}