#include <bits/stdc++.h>
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define all(x) x.begin(),x.end()
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
typedef long long ll;
long long a[N];
int L[N],R[N];
int s[N],n;
struct eveblock {
    int bel[N];
    vector<pii> v[505];
    int mx[505][505];
    int mi[505][505];
    int blo,nall;
    void build() {
        blo = sqrt(n);
        for(int i = 1; i <= n; i++) {
            bel[i] = (i + blo - 1) / blo;
            v[bel[i]].push_back({a[i], i});
        }
        nall = bel[n];
        for(int i = 1; i <= nall; i++) sort(v[i].begin(), v[i].end());
        for(int i = 1; i <= nall; i++) {
            int m = v[i].size();
            for(int j = m - 1; j >= 0; j--) mx[i][j] = max(mx[i][j + 1], v[i][j].second),mi[i][j] = INF;
            mi[i][m] = INF;
            for(int j = m - 1; j >= 0; j--) mi[i][j] = min(mi[i][j + 1], v[i][j].second);
        }
    }
    int queryleft(int l, int r, int w) {
        int ans = l - 1;
        if(l > r) return -1;
        int lb = (l + blo - 1) / blo;
        int rb = (r + blo - 1) / blo;
        if(lb == rb) {
            for(int i = r; i >= l; i--) {
                if(a[i] > w) {
                    return i;
                }
            }
        } else {
            int now = lb;
            for(int i = l; i <= min(lb * blo, n); i++) {
                if(a[i] > w) ans = max(i, ans);
            }
            now++;
            for(int i = now; i <= rb - 1; i++) {
                auto it = lower_bound(v[i].begin(), v[i].end(), make_pair(w, 0));
                if(it == v[i].end()) continue;
                else {
                    int p = lower_bound(v[i].begin(), v[i].end(), make_pair(w, 0)) - v[i].begin();
                    ans = max(mx[i][p], ans);
                }
            }
            for(int i = (rb - 1) * blo + 1; i <= r; i++) {
                if(a[i] > w) ans = max(i, ans);
            }
        }
        return ans;
    }
    int queryright(int l, int r, int w) {
        int ans = r + 1;
        if(l > r) return -1;
        int lb = (l + blo - 1) / blo;
        int rb = (r + blo - 1) / blo;

        if(lb == rb) {
            for(int i = r; i >= l; i--) {
                if(a[i] > w) {
                    ans = min(i, ans);
                }
            }
        } else {
            int now = lb;
            for(int i = l; i <= min(lb * blo, n); i++) {
                if(a[i] > w) ans = min(i, ans);
            }
            now++;
            for(int i = now; i <= rb - 1; i++) {
                auto it = lower_bound(v[i].begin(), v[i].end(), make_pair(w, 0));
                if(it == v[i].end()) continue;
                else {
                    //cout << (*it).first << " " << (*it).second << "\n";
                    int p = lower_bound(v[i].begin(), v[i].end(), make_pair(w, 0)) - v[i].begin();
            
                    ans = min(mi[i][p], ans);
                }
            }
            for(int i = (rb - 1) * blo + 1; i <= r; i++) {

                if(a[i] > w) ans = min(i, ans);
            }
        }
        if(ans == INF) return -1;
        return ans;
    }
    void test() {
       // cout << queryright(2, 5, 3);
    }
}block;
int main() {
#ifdef INCTRY
    freopen("input.txt", "rt", stdin);
#endif
    cin >> n;
    int top = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    block.build();
    block.test();
    
    a[0] = INF;
    a[n + 1] = INF; L[1] = 1; R[n] = n;
    s[0] = 0;
    for(int i = 1; i <= n + 1; i++) {
        while (a[i] > a[s[top]]) {
            top--;
        }
        L[i] = s[top] + 1;
        s[++top] = i;
    }
    fill(s, s + n + 2, 0); s[0] = n + 1; top = 0;
    for(int i = n; i >= 0; i--) {
        while(a[i] > a[s[top]]) {
           top--;
        }
        R[i] = s[top] - 1;
        s[++top] = i;
    }

    long long sum = 0;
    a[0] = a[n + 1] = 0;
    for(ll i = 1; i <= n; i++) {
        ll l = L[i], r = R[i];
        long long tot = 0;
        if(l - 1 >= 1) {
            ll ln = L[l - 1];
            ll p = block.queryleft(ln, l - 2, a[i]);
           // ll lsum = p + 1 <= l - 1 ? (l - 1 - (p + 1) + 1) : 
         //  cout << i << " " << ln << " " << p + 1 << " " << l - 1 << " ";
            if(p + 1 > l - 1) p = -1;
            if(p == -1) tot = (r - i + 1) * a[i]; // [p + 1, l - 1]
            else
            tot = (l - 1 - (p + 1) + 1) * (r - i + 1) * a[i];
        //    cout << tot << "\n";
            sum += tot;
        }
        if(r + 1 <= n) {
            ll rn = R[r + 1];
            ll p = block.queryright(r + 2, rn, a[i]);
           // cout << i << " " << rn << " " << r + 1 << " " << p - 1 << " "; // [r + 1, p - 1]
          //  if(p == -1) p = rn + 1;
            if(r + 1 > p - 1) p = -1;
            if(p == -1) tot = (i - l + 1) * a[i];
            else
            tot = (p - 1 - (r + 1) + 1) * (i - l + 1) * a[i];
           // cout << tot << "\n";
            sum += tot;
        }
    }
    cout << sum;
    return 0;
}

Measured memory_bytes: 5504