/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#pragma GCC optimize ("O2")
#pragma GCC optimize ("tree-vectorize")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class ESecondSum {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        int N;
        in>>N;
        const int INF = ten(9);
        vc<int> P(N+4);
        P[0] = P[N+3] = 2 * INF;
        P[1] = P[N+2] = INF;
        REP(i, N) in>>P[i+2];
        vvc<int> left(N+4, vc<int>(2));
        vvc<int> right(N+4, vc<int>(2));
        vc<int> pool;
        stack<int> st1, st2;
        st1.push(1); st2.push(0);
        FOR(i, 2, N+2){
            while(P[st1.top()]<P[i]){
                pool.pb(st1.top());
                st1.pop();
            }
            while(st2.top()>=st1.top()) st2.pop();
            while(P[st2.top()]<P[i]){
                st2.pop();
            }
            left[i][0] = st1.top();
            left[i][1] = max(st2.top(), 1);
            st2.push(st1.top());
            st1.push(i);
            reverse(ALL(pool));
            for(auto& p : pool){
                st2.push(p);
            }
            pool.clear();
        }
        while(not st1.empty()) st1.pop();
        while(not st2.empty()) st2.pop();
        st1.push(N+2); st2.push(N+3);
        for(int i=N+1;1<i;--i){
            while(P[st1.top()]<P[i]){
                pool.pb(st1.top());
                st1.pop();
            }
            while(st2.top()<=st1.top()) st2.pop();
            while(P[st2.top()]<P[i]){
                st2.pop();
            }
            right[i][0] = st1.top();
            right[i][1] = min(st2.top(), N+2);
            st2.push(st1.top());
            st1.push(i);
            reverse(ALL(pool));
            for(auto& p : pool){
                st2.push(p);
            }
            pool.clear();
        }
        lint ans = 0;
        FOR(i, 2, N+2){
            ans += 1ll * P[i] * (left[i][0]-left[i][1]) * (right[i][0]-i);
            ans += 1ll * P[i] * (i-left[i][0]) * (right[i][1]-right[i][0]);
        }
        out<<ans<<'\n';
    }
};


int main() {
	ESecondSum solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 15068