// #define CPP_IO

#pragma region

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxheap = priority_queue<T>;

#define f first
#define s second

#ifdef LOCAL
#define debug cout
#define debugf(format, ...) printf(format, ##__VA_ARGS__)
#else
#define debug \
    if (0) cout
#define debugf(format, ...) 42
#endif

#define DUMP(a) debug << #a " = " << (a) << "\n";
#define DUMP2(a, b) debug << #a " = " << (a) << " " #b " = " << (b) << "\n";
#define DUMP3(a, b, c) debug << #a " = " << (a) << " " #b " = " << (b) << " " #c " = " << (c) << "\n";
#define DUMP4(a, b, c, d) debug << #a " = " << (a) << " " #b " = " << (b) << " " #c " = " << (c) << " " #d " = " << (d) << "\n";

template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    os << "[ ";
    for (auto e : v) os << e << " ";
    return os << "]";
}

template <typename T, typename V>
ostream& operator<<(ostream& os, set<T, V> v) {
    os << "{ ";
    for (auto e : v) os << e << " ";
    return os << "}";
}

template <typename T, typename V, typename S>
ostream& operator<<(ostream& os, map<T, V, S> v) {
    os << "{ ";
    for (auto e : v) os << e << " ";
    return os << "}";
}

template <typename T, typename V>
ostream& operator<<(ostream& os, pair<T, V> x) {
    return os << "( " << x.first << ", " << x.second << " )";
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& e : v) is >> e;
    return is;
}

template <typename T, typename V>
istream& operator>>(istream& is, pair<T, V>& x) {
    return is >> x.first >> x.second;
}

void solve();

int main() {
#ifdef LOCAL
    freopen("data.txt", "r", stdin);
#else
#ifdef CPP_IO
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
#endif
    solve();
}

#pragma endregion

const int LOG = 20;
int n, A[100005], m[100005][20];

// maximum in [l, r]
int query(int l, int r) {
    int k = 32 - __builtin_clz(r - l + 1) - 1;
    int ans = A[m[l][k]] > A[m[r - (1 << k) + 1][k]] ? m[l][k] : m[r - (1 << k) + 1][k];
    // DUMP3(l, r, ans);
    return ans;
}

void build() {
    for (int i = 1; i <= n; ++i) m[i][0] = i;
    for (int k = 1; k < LOG; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (i + (1 << k) - 1 > n) continue;
            int x = i + (1 << (k - 1));
            if (A[m[i][k - 1]] > A[m[x][k - 1]])
                m[i][k] = m[i][k - 1];
            else
                m[i][k] = m[x][k - 1];
        }
    }
}

int boundr(int l, int v) {
    if (l == n + 1) return n + 1;
    if (A[query(l, n)] <= v) {
        return n + 1;
    }
    int lo = l, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (A[query(l, mid)] > v) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int boundl(int r, int v) {
    if (r == 0) return 0;
    debugf("boundl(%d, %d)\n", r, v);
    if (A[query(1, r)] <= v) {
        return 0;
    }
    int lo = 1, hi = r;
    while (lo < hi) {
        int mid = hi - (hi - lo) / 2;
        if (A[query(mid, r)] > v) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    return lo;
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &A[i]);
    }
    build();
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        int v = A[i];
        DUMP2(i, v);
        int r = boundr(i + 1, v);
        int r2 = n + 1;
        if (r < n)
            r2 = boundr(r + 1, v);

        DUMP2(r, r2);

        int l = boundl(i - 1, v);
        int l2 = 0;
        if (l > 0) {
            l2 = boundl(l - 1, v);
        }

        DUMP2(l, l2);

        ans += 1LL * A[i] * (r2 - r) * (i - l);
        ans += 1LL * A[i] * (l - l2) * (r - i);
        DUMP(ans);
    }
    cout << ans << "\n";
}

Measured memory_bytes: 8448