#include "bits/stdc++.h"
using namespace std;
#define MAX 1000000
#define MIN 0
int Array[100005] , MaxSegTree[400005] , MinSegTree[400005];
pair<int,int> LeftIntervals[100005] , RightIntervals[100005];

void MaxUpdate( int Node , int low , int high , int index , int value ){
    if( low == high ) MaxSegTree[Node] = value;
    else if( index < low || index > high ) return;
    else{
        int middle = ( low + high ) >> 1;
        int Temp = Node << 1;
        if( index <= middle ) MaxUpdate( Temp , low , middle , index , value );
        else MaxUpdate( Temp + 1 , middle + 1 , high , index , value );
        MaxSegTree[Node] = max( MaxSegTree[Temp] , MaxSegTree[Temp + 1] );
    }
}

void MinUpdate( int Node , int low , int high , int index , int value ){
    if( low == high ) MinSegTree[Node] = value;
    else if( index < low || index > high ) return;
    else{
        int middle = ( low + high ) >> 1;
        int Temp = Node << 1;
        if( index <= middle ) MinUpdate( Temp , low , middle , index , value );
        else MinUpdate( Temp + 1 , middle + 1 , high , index , value );
        MinSegTree[Node] = min( MinSegTree[Temp] , MinSegTree[Temp + 1] );
    }
}

int query( int Node , int low , int high , int l , int r , int which ){
    if( l <= low && r >= high ){
        if( which == 1 ) return MaxSegTree[Node];
        else return MinSegTree[Node];
    }
    else if( r < low || l > high ){
        if( which == 1 ) return MIN;
        else return MAX;
    }
    else{
        int middle = ( low + high ) >> 1;
        int Temp = Node << 1;
        int left = query( Temp , low , middle , l , r , which );
        int right = query( Temp + 1 , middle + 1 , high , l , r , which );
        if( which == 1 ) return max( left , right );
        else return min( left , right );
    }
}

void FindLeftIntervals( int N ){
    int i , index , rem;
    MaxUpdate( 1 , 1 , N , Array[1] , 1 );
    LeftIntervals[1].first = LeftIntervals[1].second = 0;

    for( i = 2 ; i <= N ; ++i ){
        MaxUpdate( 1 , 1 , N , Array[i] , i );
        
        if( Array[i] == N ){
            LeftIntervals[i].first = LeftIntervals[i].second = 0;
            continue;
        }

        index = query( 1 , 1 , N , Array[i] + 1 , N , 1 );
        
        if( index == 0 ) LeftIntervals[i].first = LeftIntervals[i].second = 0;
        else{
            LeftIntervals[i].second = index;
            rem = index;
            MaxUpdate( 1 , 1 , N , Array[index] , 0 );
            index = query( 1 , 1 , N , Array[i] + 1 , N , 1 );
            if( index == 0 ) LeftIntervals[i].first = 1;
            else LeftIntervals[i].first = index + 1; 
            MaxUpdate( 1 , 1 , N , Array[rem] , rem );
        }
    }
}

void FindRightIntervals( int N ){
    int i , index , rem;
    fill( MinSegTree , MinSegTree + 4 * N + 2 , MAX );
    MinUpdate( 1 , 1 , N , Array[N] , N );
    RightIntervals[N].first = RightIntervals[N].second = 0;

    for( i = N - 1 ; i >= 1 ; --i ){
        MinUpdate( 1 , 1 , N , Array[i] , i );

        if( Array[i] == N ){
            RightIntervals[i].first = RightIntervals[i].second = 0;
            continue;
        }

        index = query( 1 , 1 , N , Array[i] + 1 , N , 2 );

        if( index == MAX ) RightIntervals[i].first = RightIntervals[i].second = 0;
        else{
            RightIntervals[i].first = index;
            rem = index;
            MinUpdate( 1 , 1 , N , Array[index] , MAX );
            index = query( 1 , 1 , N , Array[i] + 1 , N , 2 );
            if( index == MAX ) RightIntervals[i].second = N;
            else RightIntervals[i].second = index - 1;
            MinUpdate( 1 , 1 , N , Array[rem] , rem );
        }
    }
}

long long FindAns( int N ){
    int i , l1 , d1 , l2 , d2;
    long long Ans = 0;

    for( i = 1 ; i <= N ; ++i ){
        l1 = LeftIntervals[i].second - LeftIntervals[i].first + 1;
        l2 = RightIntervals[i].second - RightIntervals[i].first + 1;
        d1 = i - LeftIntervals[i].second;
        d2 = RightIntervals[i].first - i;
        if( d2 < 0 ) d2 = N - i + 1;

        if( LeftIntervals[i].first == 0 ){
            if( RightIntervals[i].first != 0 ) Ans += Array[i] * 1LL * l2 * 1LL * d1;
        }
        else if( RightIntervals[i].first == 0 ) Ans += Array[i] * 1LL * l1 * 1LL * d2; 
        else Ans += Array[i] * ( l1 * 1LL * d2 + l2 * 1LL * d1 );
    }

    return Ans;
}

int main(){
    int N , i;
    scanf( "%d" , &N );

    for( i = 1 ; i <= N ; ++i )
        scanf( "%d" , Array + i );

    FindLeftIntervals( N );
    FindRightIntervals( N );
    printf( "%lld\n" , FindAns( N ) );
    return 0;
}

Measured memory_bytes: 4736