unittest
{
	assert( [ "3", "2 3 1" ].parse.expand.solve == 5 );
	assert( [ "5", "1 2 3 4 5" ].parse.expand.solve == 30 );
	assert( [ "8", "8 2 7 3 4 5 6 1" ].parse.expand.solve == 136 );
}



import std.container;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto ps = input.front.split.to!( long[] );
	return tuple( ps );
}

auto solve( long[] ps )
{
	// 添字と中身を逆にした配列を作成
	auto pis = new long[ 1 + ps.length ];
	pis[ 0 ] = long.min;
	foreach( i, p; ps )
	{
		pis[ p ] = i;
	}
	
	// 大きい順で処理
	auto ans = 0L;
	auto rbt = redBlackTree( -1L, pis.back, ps.length.signed );		// pより大きい値の添字をrbtに入れて二分検索できるようにする
	pis.popBack;
	for( auto p = pis.length.signed - 1; 0 < p; p-- )
	{
		// pより大きい値が1つだけ含まれる範囲を検索して、p×範囲のパターン数を計算
		auto pi = pis.back;
		pis.popBack;
		
		auto lis = rbt.lowerBound( pi ).retro.take( 2 ).array;
		auto ris = rbt.upperBound( pi ).take( 2 ).array;
		if( 1 < lis.length ) ans += p * ( ris[ 0 ] - pi       ) * ( lis[ 0 ] - lis[ 1 ] );
		if( 1 < ris.length ) ans += p * ( ris[ 1 ] - ris[ 0 ] ) * ( pi       - lis[ 0 ] );
		rbt.insert( pi );
	}
	return ans;
}
