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

using namespace std;
//fold
#define ll long long
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define Loop(i, a, b) for(int i = a ; i < b ; ++i)
#define loop(i, n) Loop(i, 0, n)
#define ff first
#define ss second
#define mkp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pii>
#define vvii vector<vii>
#define vl vector<ll>
#define pll pair<ll, ll>
#define vll vector<pll>
#define vvll vector<vll>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define nmbr(c) (int)(c-'0')
#define ltr(c) (int)(c-'a')
#define INF 1e18+5
#define inf 1e9+5
#define M 1000000007 //check
#define _69e27 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define trace(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

template <typename T> T max(T a, T b, T c){ return max(a, max(b, c));}
template <typename T> T min(T a, T b, T c){ return min(a, min(b, c));}
//endfold


const int maxn = 1e5 + 5;
int v[maxn], n, st[4*maxn];
bool f1, f2;

int left(int index){return index*2;}
int right(int index){return index*2+1;}
int mid(int l, int r){return l + (r-l)/2;}

void build(int p, int l, int r)
{
	if(l == r)
	{
		st[p] = v[l];
		return;
	}
	build(left(p), l, mid(l, r));
	build(right(p), mid(l, r)+1, r);
	st[p] = max(st[left(p)], st[right(p)]);
}

int query(int p, int l, int r, int i, int j)
{
	if(r < i || l > j) return -1;
	if(l >= i && r <= j) return st[p];
	return max(query(left(p), l, mid(l, r), i, j), query(right(p), mid(l, r)+1, r, i, j));
}

int query(int i, int j){return query(1, 0, n-1, i, j);}
int big_right(int index, int left, int right)
{
	if(left == right && v[left] > v[index]) return left;
	else if(left == right) return -1;
	int l = query(left, mid(left, right));
	if(l > v[index]) return big_right(index, left, mid(left, right));
	return big_right(index, mid(left, right)+1, right);
}
int big_left(int index, int left, int right)
{
	if(left == right && v[left] > v[index]) return left;
	else if(left == right) return -1;
	int r = query(mid(left, right)+1, right);
	if(r > v[index]) return big_left(index, mid(left, right)+1, right);
	return big_left(index, left, mid(left, right));
}
int main() {
	_69e27;
	scanf("%d", &n);
	loop(i, n) scanf("%d", &v[i]);
	build(1, 0, n-1);
	ll ans = 0;
	loop(i, n)
	{
		if(v[i] == n) continue;
		int l = big_left(i, 0, i), r = big_right(i, i, n-1);
		int l2 = (l == 0) ? -1 : l+1, r2 = (r == n-1) ? n : r-1;
		if(l != -1 && l != 0) l2 = big_left(i, 0, l-1);
		if(r != -1 && r != n-1) r2 = big_right(i, r+1, n-1);
		if(r2 == -1) r2 = n;
		if(l != -1) ans += 1LL*(v[i])*(l-l2)*(((r==-1) ? n:r) -i);
		if(r != -1) ans += 1LL*(v[i])*(r2-r)*(i-l);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1664