#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>

#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod eps=1e-11;
const lod pi=acos(-1);
const int oo=1<<30;
const ll loo=1ll<<62;
const int mods=1e9+7;
const int MAXN=600005;
const int INF=0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{
	int f=1,x=0; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
	while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
	return x*f;
}
int n;
struct Segment_Tree
{
	struct treenode{int l,r,sum,mx; } tree[MAXN<<2];
	void up(int x)
	{
		tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
		if (tree[x].sum>0) tree[x].mx=max(tree[x<<1].mx,tree[x<<1|1].mx);
		else tree[x].mx=-INF;
	}
	void build(int x,int l,int r)
	{
		if ((tree[x].l=l)==(tree[x].r=r)) 
		{
			tree[x].mx=-INF;
			return;
		}
		int mid=(l+r)>>1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		up(x);
	}
	void change(int x,int y,int z,int id)
	{
		if (tree[x].l==tree[x].r)
		{
			tree[x].sum+=z;
			if (tree[x].sum>0) tree[x].mx=id;
			else tree[x].mx=-INF;
			return;
		}
		int mid=(tree[x].l+tree[x].r)>>1;
		if (y<=mid) change(x<<1,y,z,id);
		else change(x<<1|1,y,z,id);
		up(x);
	}
	int query(int x,int l,int r)
	{
		if (tree[x].l>=l&&tree[x].r<=r) return tree[x].mx;
		int mid=(tree[x].l+tree[x].r)>>1;
		if (r<=mid) return query(x<<1,l,r);
		else if (l>mid) return query(x<<1|1,l,r);
		else return max(query(x<<1,l,mid),query(x<<1|1,mid+1,r));
	}
} tree1,tree2;
int a[MAXN],lst[MAXN],nxt[MAXN],Lst[MAXN],Nxt[MAXN];
int main()
{
    n=read();
    tree1.build(1,1,n);
    tree2.build(1,1,n);
    for (int i=1,q,p;i<=n;i++)
    {
    	a[i]=read();
    	lst[i]=tree1.query(1,a[i],n);
    	if (lst[i]==-INF) lst[i]=Lst[i]=0;
    	else
    	{
			tree1.change(1,a[lst[i]],-1,0);
			Lst[i]=tree1.query(1,a[i],n);
			if (Lst[i]==-INF) Lst[i]=0;
			tree1.change(1,a[lst[i]],1,lst[i]);
		}
		tree1.change(1,a[i],1,i);
	}
    for (int i=n,q,p;i>=1;i--)
    {
    	nxt[i]=-tree2.query(1,a[i],n);
//    	cout<<nxt[i]<<endl;
    	if (nxt[i]==INF) nxt[i]=Nxt[i]=n+1;
    	else
    	{
			tree2.change(1,a[nxt[i]],-1,0);
			Nxt[i]=-tree2.query(1,a[i],n);
			if (Nxt[i]==INF) Nxt[i]=n+1;
			tree2.change(1,a[nxt[i]],1,-nxt[i]);
		}
		tree2.change(1,a[i],1,-i);
	}
	ll ans=0;
//	for (int i=1;i<=n;i++) cout<<i<<" "<<lst[i]<<" "<<nxt[i]<<" "<<Lst[i]<<" "<<Nxt[i]<<endl;
	for (int i=1;i<=n;i++)
	{
		ans+=1ll*(1ll*(i-lst[i])*(Nxt[i]-nxt[i])+1ll*(nxt[i]-i)*(lst[i]-Lst[i]))*a[i];
//		cout<<(i-lst[i])*(Nxt[i]-nxt[i]);
//		cout<<" "<<(nxt[i]-i)*(lst[i]-Lst[i])<<endl;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 21120