import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T rtype(T)(){ return read.to!T; } alias rint = rtype!int, rlong = rtype!long, rreal = rtype!real;
T[] rtypes(T)(int n){ return n.iota.map!(i => rtype!T()).array; } alias rint = rtypes!int, rlong = rtypes!long, rreal = rtype!real;
// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //

const long infty = 1_000_009;

void solve(){
	int n = rint;
	int[] ps = rint(n);
	
	S marge(S p, S q){
		return S(max(p.best, q.best), max(min(p.best, q.best), max(p.next, q.next)));
	}
	S neginf = S(-infty, -infty);
	SegTree!S seg = new SegTree!S(0, n, &marge, neginf);
	foreach(int i, p; ps){
		seg.setValue(i, S(p, -infty));
	}
	log("seg:", seg);
	
	long ans;
	foreach(int i, p; ps){
		int l2 = downlimit!int(0, i, x => (seg.getValue(x, i + 1).best == ps[i]));
		int l1 = downlimit!int(0, l2 - 1, x => (seg.getValue(x, i + 1).next == ps[i]));
		int r1 = uplimit!int(i, n - 1, x => (seg.getValue(i, x + 1).best == ps[i]));
		int r2 = uplimit!int(r1 + 1, n - 1, x => (seg.getValue(i, x + 1).next == ps[i]));
		long tmp = (l2 - l1) * (r1 + 1 - i) + (r2 - r1) * (i + 1 - l2);
		log("i:", i, "p:", p, "l1:", l1, "l2:", l2, "r1:", r1, "r2:", r2);
		log("   ", (l2 - l1), " * ", (r1 + 1 - i), " + ", (r2 - r1), " * ", (i + 1 - l1), "tmp:", tmp);
		ans += tmp * p;
	}
	
	ans.writeln;
}

struct S{
	int best, next;
}

class SegTree(T){
	T value;
	T neutral;
	SegTree left, right; // 左の子(a <= x < c)、右の子(c <= x < b)
	bool hasValue;
	bool isTerminal;
	int a, b; // a <= x < b を担当する
	T delegate(T, T) marge;
	this(int a, int b, T delegate(T, T) marge, T neutral = T.init){
		this.a = a, this.b = b;
		this.marge = marge;
		this.neutral = neutral;
		if(b - a == 1){
			this.isTerminal = 1;
		}
		else{
			int c = (a + b) / 2;
			this.left = new SegTree(a, c, marge, neutral);
			this.right = new SegTree(c, b, marge, neutral);
		}
	}
	
	// [a, b) における値を読む ※[a, b) はこのノードの担当区間とかぶっていなくてもよい
	T getValue(int a, int b){
		if(b <= this.a || this.b <= a) return neutral;
		if(a <= this.a && this.b <= b){
			if(! this.hasValue){
				T v1 = this.left.getValue(a, b), v2 = this.right.getValue(a, b);
				T v = marge(v1, v2);
				this.value = v;
				this.hasValue = 1;
			}
			return this.value;
		}
		else{
			T v1 = this.left.getValue(a, b), v2 = this.right.getValue(a, b);
			T v = marge(v1, v2);
			return v;
		}
	}
	
	
	// i における値を設定
	void setValue(int i, T value){
		assert(a <= i && i < b);
//		this.hasValue = 0; // これが漏れていた！！
		if(this.isTerminal){
			this.hasValue = 1;
			this.value = value;
		}
		else if(i < left.b) left.setValue(i, value);
		else right.setValue(i, value);
	}
	
	// 配列に変換したもの（デバッグ用）
	T[] array(){
		if(this.isTerminal) return [this.value];
		else return this.left.array ~ this.right.array;
	}
	
	// 文字列に変換したもの（デバッグ用）
	override string toString(){
		return this.array.to!string;
	}
}


	// 二分探索テンプレート
	T uplimit(T)(T a, T c, bool delegate(T) f){
		if(f(c)) return c; if(! f(a)) return a - 1;
		while(a + 1 < c){ T b = (a + c) / 2; if(f(b)) a = b; else c = b; }
		return a;
	}
	T downlimit(T)(T a, T c, bool delegate(T) f){
		if(f(a)) return a; if(! f(c)) return c + 1;
		while(a + 1 < c){ T b = (a + c) / 2; if(f(b)) c = b; else a = b; }
		return c;
	}
