import bisect
def find_left(P,position):
    N=len(P)
    left1=[-1]*N
    left2=[-1]*N
    stack=[]
    popped=[[] for i in range(len(P))]
    stack=[P[0]]
    for i in range(1,len(P)):
        while stack:
            if stack[-1]<P[i]:
                
                popped[i]+=[stack.pop()]
            else:
                left1[i]=stack[-1]
                stack+=[P[i]]
                
                break
                
        if stack==[]:
            stack+=[P[i]]
            left1[i]=-1
        if left1[i]==-1:
            left2[i]==-1
        else:
            val=left1[i]
            pos=position[val]
            big_val_pos=len(popped[pos])
            if popped[pos]:
                big_val_pos=bisect.bisect_left(popped[pos],P[i])
                if big_val_pos<len(popped[pos]):
                    left2[i]=popped[pos][big_val_pos]
            
            #for x in popped[pos]:
            #    if x>P[i]:
            #        left2[i]=x
            #        break
                    
            
                    
            if left2[i]==-1:
                if len(stack)>=3:
                    left2[i]=stack[-3]
    return left1,left2


def find_right(P,position):
    right1,right2=find_left(P[::-1],position)
    return right1[::-1],right2[::-1]

P=list(map(int,input().strip().split(" ")))



N=len(P)
P=[p-1 for p in P]
position=[0]*len(P)
for i in range(len(P)):
    position[P[i]]=i

left1,left2=find_left(P,position)
right1,right2=find_right(P,position)

for i in range(N):
    if left1[i]!=-1:
        left1[i]=position[left1[i]]
    if left2[i]!=-1:
        left2[i]=position[left2[i]]
    
    if right1[i]==-1:
        right1[i]=N
    else:
        right1[i]=position[right1[i]]
    
    if right2[i]==-1:
        right2[i]=N
    else:
        right2[i]=position[right2[i]]
#print(P)
#print(left1,left2)
#print(right1,right2)

ans=0
for i in range(N):
    L1,L2,R1,R2=left1[i],left2[i],right1[i],right2[i]
    val=P[i]+1
    if val==N:
        continue
    temp=0
    if L1==-1:
        temp+=(i+1)*(R2-R1)
    elif R1==N:
        temp+=(L1-L2)*(N-i)
    else:
        temp+=(L1-L2)*(R1-i)
        temp+=(i-L1)*(R2-R1)
    ans+=temp*val
print(ans)
        
    



### FIXED CODE ###

import bisect
def find_left(P,position):
    N=len(P)
    left1=[-1]*N
    left2=[-1]*N
    stack=[]
    popped=[[] for i in range(len(P))]
    stack=[P[0]]
    for i in range(1,len(P)):
        while stack:
            if stack[-1]<P[i]:
                
                popped[i]+=[stack.pop()]
            else:
                left1[i]=stack[-1]
                stack+=[P[i]]
                
                break
                
        if stack==[]:
            stack+=[P[i]]
            left1[i]=-1
        if left1[i]==-1:
            left2[i]==-1
        else:
            val=left1[i]
            pos=position[val]
            big_val_pos=len(popped[pos])
            if popped[pos]:
                big_val_pos=bisect.bisect_left(popped[pos],P[i])
                if big_val_pos<len(popped[pos]):
                    left2[i]=popped[pos][big_val_pos]
            #for x in popped[pos]:
            #    if x>P[i]:
            #        left2[i]=x
            #        break
                    
            
            
            if left2[i]==-1:
                if len(stack)>=3:
                    left2[i]=stack[-3]
    #print(popped)
    return left1,left2


def find_right(P,position):
    position=[len(P)-x-1 for x in position]
    right1,right2=find_left(P[::-1],position)
    return right1[::-1],right2[::-1]
input()
P=list(map(int,input().strip().split(" ")))



N=len(P)
P=[p-1 for p in P]
position=[0]*len(P)
for i in range(len(P)):
    position[P[i]]=i

left1,left2=find_left(P,position)
right1,right2=find_right(P,position)

for i in range(N):
    if left1[i]!=-1:
        left1[i]=position[left1[i]]
    if left2[i]!=-1:
        left2[i]=position[left2[i]]
    
    if right1[i]==-1:
        right1[i]=N
    else:
        right1[i]=position[right1[i]]
    
    if right2[i]==-1:
        right2[i]=N
    else:
        right2[i]=position[right2[i]]
        
#print(P)
#print(left1,left2)
#print(right1,right2)

ans=0
for i in range(N):
    L1,L2,R1,R2=left1[i],left2[i],right1[i],right2[i]
    val=P[i]+1
    if val==N:
        
        continue
    temp=0
    if L1==-1:
        temp+=(i+1)*(R2-R1)
    elif R1==N:
        temp+=(L1-L2)*(N-i)
    else:
        temp+=(L1-L2)*(R1-i)
        temp+=(i-L1)*(R2-R1)
    
    ans+=temp*val
    
print(ans)