#include <cstdio>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(void) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    vector<int> idx(n);
    for (int i = 0; i < n; i++) {
        idx[a[i]] = i;
    }

    set<int> s;
    ll ans = 0;
    for (int x = n - 1; x >= 0; --x) {
        int i = idx[x];
        ll c = 0;

        { // calc c
            s.insert(i);
            vector<int> l(2, -1);
            vector<int> r(2, n);
            {// calc l
                auto it = s.find(i);
                for (int j = 0; j < 2; j++) {
                    if (it == s.begin()) break;
                    --it;
                    l[j] = *it;
                }
            }
            {// calc r
                auto it = s.find(i);
                for (int j = 0; j < 2; j++) {
                    ++it;
                    if (it == s.end()) break;
                    r[j] = *it;
                }
            }

            vector<int> ls(2);
            ls[0] = i - l[0];
            ls[1] = l[0] - l[1];
            vector<int> rs(2);
            rs[0] = r[0] - i;
            rs[1] = r[1] - r[0];
            c = (ll) ls[0] * rs[1] + (ll) ls[1] * rs[0];
        }

        ans += c * (x + 1);
    }
    cout << ans << endl;
}