#include <bits/stdc++.h>

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const int inf = 1e9;
const int maxn = 1e5+5;
int n, A[maxn], tree[maxn*2];

void build(const int n)
{
    for (int i = n-1; i > 0; --i)
        tree[i] = max(tree[lc(i)], tree[rc(i)]);
}

/* max on interval [i,j) */
int query(int i, int j, const int n)
{
    int ans = -inf;
    for (i += n, j += n; i < j; i >>= 1, j >>= 1) {
        if (i&1) ans = max(ans, tree[i++]);
        if (j&1) ans = max(ans, tree[--j]);
    }
    return ans;
}

int searchL(const int i, const int val)
{
    int lo = 0, hi = i;
    while (lo < hi) {
        const int mid = lo + (hi-lo+1)/2;
        if (query(mid,i+1,n) > val)
            lo = mid;
        else
            hi = mid-1;
    }
    return hi;
}

int searchR(const int i, const int val)
{
    int lo = i, hi = n;
    while (lo < hi) {
        const int mid = lo + (hi-lo)/2;
        if (query(i,mid+1,n) > val)
            hi = mid;
        else
            lo = mid+1;
    }
    return lo;
}

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n) {
        n++; A[0] = A[n] = inf;
        FOR(i,1,n) 
            cin >> A[i];
        n++;
        FOR(i,0,n) 
            tree[i+n] = A[i];
        build(n);
        LL ans = 0;
        FOR(i,1,n) {
            const int j = searchL(i,A[i]);
            if (A[j] > A[i] && A[j] < inf) {
                const int x = searchL(max(0,j-1),A[i]);
                const int y = searchR(i,A[i]);
                const int a = j-x;
                const int b = y-i;
                ans += 1LL*a*b*A[i];
            }
            const int k = searchR(i,A[i]);
            if (A[k] > A[i] && A[k] < inf) {
                const int x = searchL(i,A[i]);
                const int y = searchR(min(n,k+1),A[i]);
                const int a = i-x;
                const int b = y-k;
                ans += 1LL*a*b*A[i];
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 1408