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

#include <iostream>
#include <fstream>
//<editor-fold desc="definitions">
#include <bits/stdc++.h>
#define se cout << "test ok" << endl;
#define sp << " " <<
#define enl "\n"
using namespace std;
using ll=long long;
using ld=long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using viii = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
using vlll = vector<vector<vector<ll>>>;
using vc = vector<char>;
using vcc = vector<vector<char>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
ll mod = ll(1e9)+7;
ll inf = ll(1e18);
void bl(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void bl2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
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; }
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

#define TO_STRING(varName) # varName
#include <iostream>
#include <vector>
#include <map>
using namespace std;

namespace dbg {
    using ll = long long;

    class Debug {
        void prefix(string s){
            cout << "\033[7m\033[35m" << " DEBUG " << "\033[0m\033[35m"
            << " " << s << "\033[0m" << endl;
        }
    public:
        Debug(){}
        // vector d1
        template<typename T>
        void print(vector<T> &vec);

        // vector tuple
        template<typename T1, typename T2>
        void print(vector<pair<T1, T2>>& vec, int idx = 0);

        // vector d2
        template<typename T>
        void print(vector<vector<T>>& vec);

        // vector d2
        template<typename T>
        void print(vector<vector<vector<T>>>& vec);

        // vector array d1
        template<typename T>
        void print(T *arr, ll n);

        // vector array d2
        template<typename T>
        void print(T *arr, int n, int m);

        // set
        template<typename T>
        void print(set<T>& st);

        // vector map or set
        template<typename T>
        void print(T cont);
    };

    template<typename T>
    void Debug::print(vector<T>& vec) {
        prefix("vector");
        for (auto& v : vec) cout << v << " ";
        cout << endl;
    }

    template<typename T1, typename T2>
    void Debug::print(vector<pair<T1, T2>>& vec, int idx) {
        prefix("vector pair");
        for (auto& v : vec) cout << (!idx ? get<0>(v) : get<1>(v)) << " ";
        cout << endl;
    }

    template<typename T>
    void Debug::print(vector<vector<T>>& vec) {
        prefix("vector d2");
        for (auto& vv : vec) {
            for (auto& v : vv) cout << v << " ";
            cout << endl;
        }
    }

    template<typename T>
    void Debug::print(vector<vector<vector<T>>>& vec) {
        prefix("vector d3");
        for(auto& vvv : vec) {
            cout << "[";
            for(int i=0; i<vvv.size(); i++) {
                if(i) cout << " ";
                for(int j=0; j<vvv[i].size(); j++) {
                    if(j) cout << " ";
                    cout << vvv[i][j];
                }
                if(i != vvv.size()-1) cout << endl;
            }
            cout << "]" << endl;
        }
    }

    template<typename T>
    void Debug::print(T *arr, ll n) {
        prefix("array");
        for (int i = 0; i < n; i++) cout << arr[i] << " ";
        cout << endl;
    }

    template<typename T>
    void Debug::print(T *arr, int n, int m) {
        prefix("array d2");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << arr[i][j] << " ";
            }
            cout << endl;
        }
    }

    template<typename T>
    void Debug::print(set<T>& st) {
        prefix("set");
        for(auto& e : st) cout << e << " ";
        cout << endl;
    }

    template<typename T>
    void Debug::print(T cont) {
        prefix("key value");
        for (auto& e : cont)
            cout << e.first << " : " << e.second << endl;
        cout << endl;
    }

}

#endif //INCLUDE_DEBUG_HPP

dbg::Debug debug;
//</editor-fold>

class ESecondSum {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int n;
	    in >> n;
	    vl p(n), ip(n);
	    for(int i=0; i<n; i++) {
	        in >> p[i], --p[i];
	        ip[p[i]] = i;
	    }

	    ll res = 0;
	    set<int> st;
	    st.insert(-2); st.insert(-1);
	    st.insert(n); st.insert(n+1);
	    for(int i=n-1; i>=0; i--){
            int x = ip[i];
            auto it = st.lower_bound(x);
            int r = *it;
            int r2 = *(++it);
            --it;
            int l = *(--it);
            int l2 = *(--it);

            ll buf = 0;
            if(r!=n) buf += (x-l) * (r2-r);
            if(l!=-1) buf += (r-x) * (l-l2);
            res += buf * (i+1);
            st.insert(x);
	    }

	    out << res << enl;
	}
};


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


Measured memory_bytes: 6528