#include <bits/stdc++.h>
 
#define int long long
 
#define pii pair<int, int>
 
#define x1 x1228
#define y1 y1228
 
#define left left228
#define right right228
 
#define pb push_back
#define eb emplace_back
 
#define mp make_pair                                                                
                                                                                                                                        
#define ff first                                                                  
#define ss second   
 
#define matr vector<vector<int> > 
 
#define all(x) x.begin(), x.end()
 
 
using namespace std;
typedef long long ll; 
typedef long double ld; 
                                                                                                   
const int maxn = 3e5 + 7, mod = 998244353, inf = 1e18, MAXN = 1e6 + 7;
const double eps = 1e-9;
mt19937 rnd(time(0));
int n;
int cnt[maxn];
 
vector<int> tree;
int len = 1; 

void build(int sz) {
    while (len < sz) len <<= 1; 
    tree.resize(len + len - 1); 
    for (int i = 0; i < n; ++i) {
        tree[i + len - 1] = cnt[i]; 
    }
    for (int i = len - 2; i >= 0; --i) {
        tree[i] = max(tree[i * 2 + 1], tree[i * 2 + 2]); 
    }
}

int get(int l, int r, int l1, int r1, int rt) {
    if (l >= l1 && r <= r1) {
        return tree[rt]; 
    }
    if (max(l, l1) > min(r, r1)) return -inf; 
    int tm = (l + r) / 2;
    return max(get(l, tm, l1, r1, rt * 2 + 1), get(tm + 1, r, l1, r1, rt * 2 + 2)); 
}

int binn_l(int x, int val) {
    int l = -1; 
    int m; 
    int r = x; 
    while (l + 1 < r) {
        m = (l + r) / 2;
        if (get(0, len - 1, m, x - 1, 0) > val) {
            l = m;
        } else {
            r = m; 
        }
    }
    return l; 
}

int binn_r(int x, int val) {
    int l = x; 
    int m; 
    int r = n; 
    while (l + 1 < r) {
        m = (l + r) / 2;
        if (get(0, len - 1, x + 1, m, 0) > val) {
            r = m;
        } else {
            l = m; 
        }
    }
    return r; 
}

void solve() { 
    cin >> n; 
    for (int i = 0; i < n; ++i) {
        cin >> cnt[i];
    }
    build(n); 
    int ans = 0; 
    for (int i = 0; i < n; ++i) {
        int l1 = binn_l(i, cnt[i]);
        int l2 = binn_l(l1, cnt[i]);
        int r1 = binn_r(i, cnt[i]);
        int r2 = binn_r(r1, cnt[i]);
//        cout << l1 << " " << l2 << " " << r1 << " " << r2 << endl; 
        if (l1 != -1) {
            ans += (l1 - l2) * cnt[i]; 
//            cout << ans << endl; 
//            cout << ans << endl; 
//            return; 
            ans += (l1 - l2) * (r1 - i - 1) * cnt[i]; 
        }        
        if (r1 != n) {
            ans += (r2 - r1) * cnt[i]; 
            ans += (r2 - r1) * (i - l1 - 1) * cnt[i];
        }                                              
    }
    cout << ans; 
}                                
   
signed main() {
#ifdef LOCAL
    freopen("TASK.in", "r", stdin);
    freopen("TASK.out", "w", stdout);
#else 
    
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(20); 
    cout << fixed; 
    int t = 1; 
    for (int i = 0; i < t; ++i) {              
        solve();
    }
    return 0;
}  

Measured memory_bytes: 3072