using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var a=sc.Ia3(true,int.MaxValue,true,int.MaxValue);
		Spt spt=new Spt(a);
		long ans2=0;
		for(int i = 1;i<=n;i++) {
			if(a[i]==n){continue;}
			int lb=i,ub=n+1,mid=0;
			while(ub-lb>1){
				mid=(ub+lb)/2;
				if(spt.Get(i,mid)>a[i]){ub=mid;}
				else{lb=mid;}
			}
			int r=ub;
			lb=0;ub=i;mid=0;
			while(ub-lb>1){
				mid=(ub+lb)/2;
				if(spt.Get(mid,i)>a[i]){lb=mid;}
				else{ub=mid;}
			}
			int l=lb;
			lb=r;ub=n+1;mid=0;
			while(ub-lb>1){
				mid=(ub+lb)/2;
				if(spt.Get(r+1,mid)>a[i]){ub=mid;}
				else{lb=mid;}
			}
			int r2=ub;
			lb=0;ub=l;mid=0;
			while(ub-lb>1){
				mid=(ub+lb)/2;
				if(spt.Get(mid,l-1)>a[i]){lb=mid;}
				else{ub=mid;}
			}
			int l2=lb;
			ans2+=a[i]*((long)l-l2)*(r-i);
			ans2+=a[i]*((long)i-l)*(r2-r);
		}
		Console.WriteLine("{0}",ans2);
	}
}
public class Spt{
	private readonly int[][] d;
	private readonly int[] l;
	public Spt(int[] a){
		int n=a.Length,m=(int)Log(n,2)+1;
		d=new int[m][];
		d[0]=new int[n];
		l=new int[n+1];
		for(int i=0;i<n;i++){
			d[0][i]=a[i];
			l[i+1]=l[i>>1]+1;
		}
		for(int i=1,k=1;i<m;i++,k<<=1){
			int p=n+1-(k<<1);
			d[i]=new int[p];
			for(int j=0;j<p;j++){d[i][j]=Max(d[i-1][j],d[i-1][j+k]);}
		}
	}
	public int Get(int a,int b){
		if(a>b){a^=b;b^=a;a^=b;}
		int p=l[b-a];
		return Max(d[p][a],d[p][b+1-(1<<p)]);
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 25824