Given is a permutation P of \{1, 2, \ldots, N\}.
For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.
Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

-----Constraints-----
 -  2 \le N \le 10^5 
 -  1 \le P_i \le N 
 -  P_i \neq P_j  (i \neq j)
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
P_1 P_2 \ldots P_N

-----Output-----
Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

-----Sample Input-----
3
2 3 1

-----Sample Output-----
5

X_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.

Difficulty: interview

Starter code:

Solutions:
def main():
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[i for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            temp_list=[]
            temp=self.tree[index]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index]
            for i in temp_list:
                self.tree[i]=index
            return index
        
        #結合
        def unite_r(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1<r2:
                self.tree[r1]=r2
            else:
                self.tree[r2]=r1

        def unite_l(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1>r2:
                self.tree[r1]=r2
            else:
                self.tree[r2]=r1

        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
            
    n=int(input())
    a=list(map(int,input().split()))
    d=[0]*n
    for i,j in enumerate(a):
        d[j-1]=i+2
    vis=[False]*(n+4)
    u_r=unionfind(n+4)
    u_l=unionfind(n+4)
    ans=0
    for j,i in enumerate(d[:-1]):
        vis[i]=True
        if vis[i+1]==True:
            u_r.unite_r(i,i+1)
            u_l.unite_l(i,i+1)
            k1=u_r.root(i+1)+1
        else:
            k1=i+1
        if vis[k1+1]==True:
            cnt1=u_r.root(k1+1)+1
        else:
            cnt1=k1+1
        cnt1=min(cnt1,n+2)
        if vis[i-1]==True:
            u_r.unite_r(i,i-1)
            u_l.unite_l(i,i-1)
            k2=u_l.root(i-1)-1
        else:
            k2=i-1
        if vis[k2-1]==True:
            cnt2=u_l.root(k2-1)-1
        else:
            cnt2=k2-1
        cnt2=max(cnt2,1)
        ans+=((k2-cnt2)*(k1-i)+(cnt1-k1)*(i-k2))*(j+1)
    print(ans)
main()

import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret

    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]

    def dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = SqrtSet()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()


N = int(input())
P = [int(x) for x in input().split()]

PIdx = sorted([(i + 1, v) for i, v in enumerate(P)], key = lambda x: x[1])

L = [0]
for i in range(N + 1):
    L.append(i)

R = [i + 1 for i in range(N + 1)]
R.append(N + 1)

ans = 0
for i, v in PIdx:
    l1 = L[i]
    l2 = L[l1]
    r1 = R[i]
    r2 = R[r1]

    ans += v * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))

    L[r1] = l1
    R[l1] = r1

print(ans)

N = int(input())
P = list(map(int, input().split()))
R = list(range(N))
L = list(range(N))
I = [-1] * (N+1)
for i, p in enumerate(P):
    I[p] = i

ans = 0
for n, idx in enumerate(I[1:], 1):
    l = idx-1
    while l>=0 and l!=L[l]:
        l = L[l]
    r = idx+1
    while r<N and r!=R[r]:
        r = R[r]
    L[idx] = l
    R[idx] = r

    if l != -1:
        l2 = l-1
        while l2>=0 and l2!=L[l2]:
            l2 = L[l2]
        ans += n * (l-l2) * (r-idx)
    if r != N:
        r2 = r+1
        while r2<N and r2!=R[r2]:
            r2 = R[r2]
        ans += n * (idx-l) * (r2-r)
print(ans)


n = int(input())
lst = list(enumerate(list(map(int, input().split()))))

sorted_lst = sorted(lst, key = lambda x: x[1])
left_next_index = list(range(-1, n - 1)) + [-1, -1]
right_next_index = list(range(1, n + 1)) + [n, n]

ans = 0
for i, p in sorted_lst:
    l2 = left_next_index[i]
    l1 = left_next_index[l2]
    r1 = right_next_index[i]
    r2 = right_next_index[r1]
    
    a = p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
    ans += a
    
    left_next_index[r1] = l2
    right_next_index[l2] = r1
print(ans)

n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)


from bisect import*
class SqrtSet:
    def __init__(self,block_limit=201):
        self.key=[]
        self.child=[[]]
        self.block_limit=block_limit
    def le(self,key):
        ret=key
        i=bisect_left(self.key,key)
        if i:ret=self.key[i-1]
        block=self.child[i]
        i=bisect_left(block,key)
        if i:ret=block[i-1]
        return ret
    def ge(self,key):
        ret=key
        i=bisect(self.key,key)
        if i<len(self.key):ret=self.key[i]
        block=self.child[i]
        i=bisect(block,key)
        if i<len(block):ret=block[i]
        return ret
    def insert(self,key):
        i=bisect(self.key,key)
        block=self.child[i]
        insort(block,key)
        if len(block)==self.block_limit:
            sep=self.block_limit//2
            self.key.insert(i,block[sep])
            self.child.insert(i+1,block[sep+1:])
            self.child[i]=block[:sep]
def main():
    n,*p=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(p,1):l[v-1]=i
    t=SqrtSet()
    insert,le,ge=t.insert,t.le,t.ge
    insert(0),insert(n+1)
    a=0
    for i,v in list(enumerate(l,1))[::-1]:
        f,b=ge(v),le(v)
        g,c=ge(f),le(b)
        a+=i*((f-v)*(b-c)+(v-b)*(g-f))
        insert(v)
    print(a)
main()

N = int(input())
P = list(map(int, input().split()))

index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index

left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
# print (left_next_Index)
# print (right_next_Index)
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))

    left_next_Index[r1] = l1
    right_next_Index[l1] = r1

print (ans)

class Node:
  def __init__(self, v):
    self.v = v
    self.p = None
    self.n = None
  
  def delete(self):
    if self.p:
      self.p.n = self.n
    if self.n:
      self.n.p = self.p

N = int(input())
pp = list(map(int, input().split()))
nn = dict()
prev = None
for i, p in enumerate(pp):
  n = Node(i)
  if prev:
    prev.n = n
    n.p = prev
  nn[p] = n
  prev = n
s = 0
for x in range(1, N):
  c = nn[x]
  ci = c.v
  pi = c.p.v if c.p else -1
  ni = c.n.v if c.n else N
  if c.p:
    ppi = c.p.p.v if c.p.p else -1
    s += x * (pi - ppi) * (ni - ci)
  if c.n:
    nni = c.n.n.v if c.n.n else N
    s += x * (ci - pi) * (nni - ni)
  c.delete()
print(s)

N = int(input())
P = list(map(int, input().split()))
 
left_bigger  = [0] + [i for i in range(N+1)]
right_bigger = [i+1 for i in range(N+1)] + [N+1]
 
E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v,i in E:
    l0=left_bigger[i]
    l1=left_bigger[l0]
    r0=right_bigger[i]
    r1=right_bigger[r0]
    
    ans += ((r1-r0)*(i-l0) + (r0-i)*(l0-l1))*v
    left_bigger[r0]=l0
    right_bigger[l0]=r0
print(ans)

def argsort(a):
    return list(map(lambda z: z[1], sorted(zip(a, range(len(a))))))

N = int(input())
P = list(map(int, input().split()))

a = argsort(P)
left = [i for i in range(N)]
right = [i for i in range(N)]
result = 0
for i in range(1, N):
    k = a[i - 1]
    extend_left = k - 1 >= 0 and P[k - 1] < i
    extend_right = k + 1 < N and P[k + 1] < i
    if extend_left and extend_right:
        L = left[k - 1]
        R = right[k + 1]
    elif extend_left:
        L = left[k - 1]
        R = k
    elif extend_right:
        R = right[k + 1]
        L = k
    else:
        L = k
        R = k
    right[L] = R
    left[R] = L
    if L - 1 >= 0:
        if L - 2 >= 0 and P[L - 2] < i:
            LL = left[L - 2]
        else:
            LL = L - 1
        result += ((L - 1) - LL + 1) * (R - k + 1) * i;
    if R + 1 < N:
        if R + 2 < N and P[R + 2] < i:
            RR = right[R + 2]
        else:
            RR = R + 1
        result += (RR - (R + 1) + 1) * (k - L + 1) * i;
print(result)

class Node:
    def __init__(self,  key=None):
        self.key = key
        self.height = 1
        self.parent = None
        self.left = None
        self.right = None

def get_height(t):
    return 0 if t is None else t.height

def get_balance(t):
    return get_height(t.left) - get_height(t.right)

def update_height(t):
    left_height = get_height(t.left)
    right_height = get_height(t.right)
    if left_height >= right_height:
        t.height = left_height + 1
    else:
        t.height = right_height + 1


class AVL:
    def __init__(self):
        self.root = Node()       
    
    def insert(self, key):
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node
        
        cursor = p
        while cursor:     
            balance = get_balance(cursor)
            if balance == 0:
                break
            elif balance == 2:
                if key < cursor.left.key:
                    self.rotate_r(cursor)
                else:
                    self.rotate_lr(cursor)
                break
            elif balance == -2:
                if key > cursor.right.key:
                    self.rotate_l(cursor)
                else:
                    self.rotate_rl(cursor)
                break
            else:
                update_height(cursor)
                cursor = cursor.parent
           
    def rotate_r(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc is not None:
            n.left = gc
            gc.parent = n
        else:
            n.left = None
            
        c.right = n
        n.parent = c
        
        if p is not None:    
            if p.right == n:
                p.right = c
            else:
                p.left = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)                
    
    def rotate_l(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc is not None:
            n.right = gc
            gc.parent = n
        else:
            n.right = None
            
        c.left = n
        n.parent = c
        
        if p is not None:
            if p.left == n:
                p.left = c
            else:
                p.right = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)       
      
    def rotate_rl(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc.left and gc.right:
            n.right = gc.left
            c.left = gc.right
            gc.left.parent = n
            gc.right.parent = c
        elif gc.left:
            n.right = gc.left
            gc.left.parent = n
            c.left = None
        elif gc.right:
            c.left = gc.right
            gc.right.parent = c
            n.right = None
        else:
            n.right = None
            c.left = None
            
        gc.left = n
        gc.right = c
        n.parent = gc
        c.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)

    def rotate_lr(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc.left and gc.right:
            c.right = gc.left
            n.left = gc.right
            gc.left.parent = c
            gc.right.parent = n
        elif gc.left:
            c.right = gc.left
            gc.left.parent = c
            n.left = None
        elif gc.right:
            n.left = gc.right
            gc.right.parent = n
            c.right = None
        else:
            n.left = None
            c.right = None
        gc.left = c
        gc.right = n
        c.parent = gc
        n.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)        
        
    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return None
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return None
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent              
        else:
            return None
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2
                

def main():

    N = int(input())
    P = map(int, input().split())
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
def __starting_point():
    main()
__starting_point()

n = int(input())
A = list(map(int, input().split()))
A = [a-1 for a in A]

P = [-1]*n
for i, a in enumerate(A):
    P[a] = i

#print(P)

R = [[n]*2 for _ in range(n)]
q = []
import heapq
heapq.heapify(q)
for i in range(n):
    temp = []
    while q:
        if q[0][0] < A[i]:
            v, j = heapq.heappop(q)
            R[v][j] = i
            if j == 0:
                temp.append((v, j+1))
        else:
            break
    heapq.heappush(q, (A[i], 0))
    for v, j in temp:
        heapq.heappush(q, (v, j))

#print(R)

L = [[-1]*2 for _ in range(n)]
q = []
import heapq
heapq.heapify(q)
for i in reversed(list(range(n))):
    temp = []
    while q:
        if q[0][0] < A[i]:
            v, j = heapq.heappop(q)
            L[v][j] = i
            if j == 0:
                temp.append((v, j+1))
        else:
            break
    heapq.heappush(q, (A[i], 0))
    for v, j in temp:
        heapq.heappush(q, (v, j))

#print(L)
ans = 0
for i in range(n-1):
    p = P[i]
    l1 = L[i][0]
    l2 = L[i][1]
    r1 = R[i][0]
    r2 = R[i][1]
    ans += ((l1-l2)*(r1-p)+(r2-r1)*(p-l1))*(i+1)
print(ans)


import sys,bisect as bs,collections as cl
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(list(map(max,x)))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

p = [0] + l() + [n+1]
ans = 0
a = [0 for i in range(n+2)]

for i in range(n+2):
    a[p[i]] = i

l = [set() for i in range(n+2)]
r = [set() for i in range(n+2)]

for i in range(n+2):
    l[i].add(max(0,i-1))
    l[i].add(max(0,i-2))
    r[i].add(min(n+1,i+1))
    r[i].add(min(n+1,i+2))


for i in range(n+1):
    m = a[i]
    x2,x1,y1,y2 = min(l[m]),max(l[m]),min(r[m]),max(r[m])
    hoge= i*(abs((m-x1)*(y2-y1)) + abs((y1-m)*(x1-x2)))
    ans += hoge

    r[x1].clear()
    r[x1].add(y1)
    r[x1].add(y2)

    l[y1].clear()
    l[y1].add(x1)
    l[y1].add(x2)
    
    r[x2].clear()
    r[x2].add(x1)
    r[x2].add(y1)

    l[y2].clear()
    l[y2].add(y1)
    l[y2].add(x1)
    

print(ans)




# 平方分割に勝てない～～～～～～～～～～～～～～
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (add, pop) データ構造: https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (init, add, remove, search_higher_equal) Exclusive OR Queries: https://atcoder.jp/contests/cpsco2019-s1/submissions/7488225
    # 検証3 (add, search_higher, search_lower) Second Sum: https://atcoder.jp/contests/abc140/submissions/7485479
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= (y & 0x7ffff) << 13
                y ^= y >> 17
                y ^= (y & 0x7ffffff) << 5
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        # xorshift
        y = self.rand_y
        y ^= (y & 0x7ffff) << 13
        y ^= y >> 17
        y ^= (y & 0x7ffffff) << 5
        self.rand_y = y

        if y % self.square == 0:
            layer1, layer0 = self.layer1, self.layer0
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(self.layer1, x)
            insort_right(self.layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del self.layer1[idx1]
            self.layer0[idx1] += self.layer0.pop(idx1+1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        idx1 = bisect_right(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return self.layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    inf = float("inf")
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

n = int(input())
p = list(map(int, input().split()))
lis = [0] * (n + 1)
for i in range(n):
    lis[p[i]] = i
l = list(range(-1, n - 1)) + [-1, -1]
r = list(range(1, n + 1)) + [n, n]
ans = 0
for i in range(n):
    ans += (i + 1) * ((lis[i + 1] - l[lis[i + 1]]) * (r[r[lis[i + 1]]] - r[lis[i + 1]]) + (l[lis[i + 1]] - l[l[lis[i + 1]]]) * (r[lis[i + 1]] - lis[i + 1]))
    r[l[lis[i + 1]]] = r[lis[i + 1]]
    l[r[lis[i + 1]]] = l[lis[i + 1]]
print(ans)

n = int(input())
p = list(map(int, input().split()))

pos_list = [0] * n
# print(index_list) [0, 0, 0, 0] n = 4 のとき
for index, i in enumerate(p, 0):
    # print(index, i)
    pos_list[i - 1] = index
    # print(index_list)

left_next_index = list(range(-1, n-1)) + [-1, -1]
right_next_index = list(range(1, n+1)) + [n, n]

answer = 0
# print(left_next_index)    [-1, 0, 1, -1, -1]
# print(right_next_index)   [1, 2, 3, 3, 3]
for i in range(1, n):
    index = pos_list[i-1]
    l1 = left_next_index[index]
    l2 = left_next_index[l1]
    r1 = right_next_index[index]
    r2 = right_next_index[r1]
    # print(index, l1, l2, r1, r2, i)
    answer += i * ((index-l1) * (r2-r1) + (r1-index) * (l1-l2))

    left_next_index[r1] = l1
    right_next_index[l1] = r1

print(answer)

class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N = int(input())
INF = 10**18
P = list(map(int, input().split()))
I = [-1] * (N + 1)
tree = UnionFind(N + 2)

for i, p in enumerate(P, start=1):
    I[p] = i

ans = 0
used = [False] * (N + 2)
for p in range(1, N):
    i = I[p]

    # p 未満の範囲 [i - left, i + right]
    left = tree.sizeOfSameRoot(i - 1) if used[i - 1] else 0
    right = tree.sizeOfSameRoot(i + 1) if used[i + 1] else 0

    cnt = 0
    leftMx = i - (left + 1)
    if leftMx >= 1 and not used[leftMx]:
        L = tree.sizeOfSameRoot(leftMx - 1) if (leftMx - 1) >= 0 and used[leftMx - 1] else 0
        cnt += (L + 1) * (right + 1)
    rightMx = i + (right + 1)
    if rightMx <= N and not used[rightMx]:
        R = tree.sizeOfSameRoot(rightMx + 1) if (rightMx + 1) <= N and used[rightMx + 1] else 0
        cnt += (left + 1) * (R + 1)
    ans += cnt * p

    used[i] = True
    if used[i - 1]:
        tree.union(i, i - 1)
    if used[i + 1]:
        tree.union(i, i + 1)
print(ans)


from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = [inf]
            self.layer0 = {inf: []}
        else:
            self.layer1 = layer1 = []
            if not sorted_:
                values.sort()
            rand_depth = self._rand_depth
            l0 = []
            layer0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
            self.layer0 = dict(zip([inf]+layer1, layer0))
            layer1.append(inf)

    def _rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        if self._rand_depth():
            idx1 = bisect_right(layer1, x)
            val1 = layer1[idx1-1]
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[val1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0[x] = layer0_idx1[idx0:]
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            val1 = layer1[idx1-1]
            insort_right(layer0[val1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del layer1[idx1]
            layer0[idx1] += layer0.pop(idx1+1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        val1 = layer1[idx1-1]
        layer0_idx1 = layer0[val1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        val1 = layer1[idx1-1]
        layer0_idx1 = layer0[val1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        raise NotImplementedError
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(*sorted(list(self.layer0.items())), sep="\n")


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList(square=int(n**0.5))
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


#!/usr/bin/env python3
N=int(input())
p=list(map(int,input().split()))
LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]
E = [(v, i+1) for i, v in enumerate(p)]
E.sort()
ans=0
for v, i in E:
  r0 = RR[i]
  r1 = RR[r0]
  l0 = LL[i]
  l1 = LL[l0]
  RR[l0] = r0
  LL[r0] = l0

  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

print(ans)


n = int(input())
lst = list(enumerate(list(map(int, input().split()))))
 
sorted_lst = sorted(lst, key = lambda x: x[1])
left_next_index = list(range(-1, n - 1)) + [-1, -1]
right_next_index = list(range(1, n + 1)) + [n, n]
 
ans = 0
for i, p in sorted_lst:
    l2 = left_next_index[i]
    l1 = left_next_index[l2]
    r1 = right_next_index[i]
    r2 = right_next_index[r1]
    
    a = p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
    ans += a
    
    left_next_index[r1] = l2
    right_next_index[l2] = r1
print(ans)

from collections import deque
#from heapq import heapify, heappop, heappush
from bisect import bisect_left
#from math import gcd
#from decimal import Decimal
#mod = 1000000007
#mod = 998244353
N = int(input())
#N, K = map(int, input().split())
P = list(map(int, input().split()))
#flag = True
big = []
for k in range(N):
  big.append((P[k], k+1))
big.sort(key=lambda x: x[0], reverse=True)
big = deque(big)
item = big.popleft()
done = [0,0,item[1],N+1,N+1]
ans = 0
while big:
  item = big.popleft()
  index = item[1]
  num = item[0]
  i = bisect_left(done, index)
  done.insert(i, index)
  ans += num*((done[i+2]-done[i+1])*(index - done[i-1])+ (done[i-1]-done[i-2])*(done[i+1]-index))
print(ans)
#print('Yes')
#print('No')


N = int(input())
*p, = map(int, input().split())

LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]

E = [(v,i+1) for i,v in enumerate(p)]
E.sort()

ans = 0
for v,i in E:
  r0 = RR[i]; r1 = RR[r0]
  l0 = LL[i]; l1 = LL[l0]
  RR[l0] = r0; LL[r0] = l0
  
  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

print(ans)

N = int(input())
P_id = [0]*(N + 1) # P_id[i]は順列Pに置けるiのindex, P[0]は無視
for index, p in enumerate(map(int, input().split())):
    P_id[p] = index

left_next_index = list(range(- 1, N - 1)) + ['うんこ', - 1] # + [- 1]ではないことに注意, left_next_index[r1] = l1においてr1 = Nの場合があるから
right_next_index = list(range(1, N + 1)) + [N, 'うんこ']

res = 0
for p in range(1, N):
    l1 = left_next_index[P_id[p]]
    l2 = left_next_index[l1]
    r1 = right_next_index[P_id[p]]
    r2 = right_next_index[r1]
    
    res += p*((l1 - l2)*(r1 - P_id[p]) + (P_id[p] - l1)*(r2 - r1))
    
    left_next_index[r1] = l1
    right_next_index[l1] = r1
    
print(res)

n = int(input())
P = list(map(int, input().split()))

num_idx = [0]*(n+1)

# 自分のidxからみて右側で，自身の値より大きな値をもつ，一番近いidx
right_idx_over_current_pos = list(range(1, n+1)) + [n, n]
# 自分のidxからみて左側で，自身の値より大きな値をもつ，一番近いidx
left_idx_over_current_pos = list(range(-1, n-1)) + [-1, -1]

# 1から見ていくとすると，上記2つとも，自分のすぐ隣のidxがそのまま該当する

for idx, num in enumerate(P):
    num_idx[num] = idx

ans = 0
for num in range(1, n+1):  # 小さいほうから決める
    now = num_idx[num]
    r1 = right_idx_over_current_pos[now]
    r2 = right_idx_over_current_pos[r1]
    l1 = left_idx_over_current_pos[now]
    l2 = left_idx_over_current_pos[l1]

    r_pattern = (r2-r1) * (now-l1)
    l_pattern = (l1-l2) * (r1-now)

    right_idx_over_current_pos[l1] = r1  # l1にある値 > nowからr1までにある値 なので nowをスキップして r1までいける
    left_idx_over_current_pos[r1] = l1  # 上の左向きver
    ans += (r_pattern + l_pattern) * num

print(ans)


from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = TwoLayerSet(1/1000)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()


N = int(input())
*P, = map(int, input().split())

LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]

E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v, i in E:
    l0 = LL[i]; l1 = LL[l0]

    r0 = RR[i]; r1 = RR[r0]

    LL[RR[i]], RR[LL[i]] = LL[i], RR[i]

    ans += ((r1 - r0) * (i - l0) + (r0 - i) * (l0 - l1)) * v
print(ans)

#!/usr/bin/env python3
ans=0
n=int(input())
p=list(map(int,input().split()))
b=[0]*(n+1)
for i in range(n):
    b[p[i]]=i+1
LL=[0]+[i for i in range(n+1)]
RR=[i for i in range(1,n+2)]+[n+1]
for i in range(1,n+1):
    l1=LL[b[i]]
    l0=LL[l1]
    r0=RR[b[i]]
    r1=RR[r0]
    ans+=((l1-l0)*(r0-b[i])+(r1-r0)*(b[i]-l1))*i
    LL[r0]=l1
    RR[l1]=r0

print(ans)


from operator import itemgetter


def solve(n, ppp):
    qqq = sorted(enumerate(ppp), key=itemgetter(1))
    left_next_index = list(range(-1, n - 1)) + [-1, -1]
    right_next_index = list(range(1, n + 1)) + [n, n]
    ans = 0
    for i, p in qqq:
        l2 = left_next_index[i]
        l1 = left_next_index[l2]
        r1 = right_next_index[i]
        r2 = right_next_index[r1]
        ans += p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
        left_next_index[r1] = l2
        right_next_index[l2] = r1
    return ans


n = int(input())
ppp = list(map(int, input().split()))
print((solve(n, ppp)))


import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)


3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12(i, j):
        if j - i <= 0:
            return (0, 0)

        segi = 0
        top = []

        while True:
            if j - i <= 0:
                break

            seg = segt[segi]

            if j - i == 1:
                top.extend(seg[i])
                break

            if i % 2 == 1:
                top.extend(seg[i])
                i += 1
            if j % 2 == 1:
                top.extend(seg[j - 1])
                j -= 1

            i //= 2
            j //= 2
            segi += 1

        top.sort()
        return top[-1], top[-2]

    cache = [dict() for _ in range(N)]

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if j in cache[i]:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or d in cache[c]):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[c][d]
                                    for c, d in want]
                cache[i][j] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[c][d]
                            for c, d in want]
        cache[i][j] = left + right - mid + sc

    return cache[0][N]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


def __starting_point():
    main()

__starting_point()

n = int(input())
aa = list(map(int, input().split()))
ans = 0
pos = [0] * (n + 1)

for i, a in enumerate(aa):
    pos[a] = i + 2
Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
for a in range(1,n + 1):
    i = pos[a]
    l0 = Lnext[i]
    l1 = Lnext[l0]
    r0 = Rnext[i]
    r1 = Rnext[r0]
    ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
    Lnext[r0] = l0
    Rnext[l0] = r0
print(ans)

from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (データ構造): https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (Exclusive OR Queries): https://atcoder.jp/contests/cpsco2019-s1/submissions/7479914
    # 検証3 (Second Sum): https://atcoder.jp/contests/abc140/submissions/7480312
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        if self.rand_depth():
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        #res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて res で埋まっている場合
            return layer1[idx1-1]
        else:
            return layer0_idx1[idx0-1]
        # if res != x:  # res > x
        #     if layer0_idx1:
        #         idx0 = bisect_left(layer0_idx1, x)
        #         if idx0 != 0:
        #             return layer0_idx1[idx0-1]
        #     return layer1[idx1-1]  # layer0_idx1 が空の場合とすべて x 以上の場合
        # else:
        #     idx0 = bisect_left(layer0_idx1, x)
        #     if idx0 == 0:  # layer0_idx1 が空の場合とすべて res で埋まっている場合
        #         return layer1[idx1-1]
        #     else:
        #         return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め  使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


N = int(input())
P = list(map(int, input().split()))
 
left_bigger  = [0] + [i for i in range(N+1)]
right_bigger = [i+1 for i in range(N+1)] + [N+1]
 
E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v,i in E:
    l0=left_bigger[i]
    l1=left_bigger[l0]
    r0=right_bigger[i]
    r1=right_bigger[r0]
    ans += ((r1-r0)*(i-l0) + (r0-i)*(l0-l1))*v
    left_bigger[r0]=l0
    right_bigger[l0]=r0
print(ans)




# 参考 https://atcoder.jp/contests/abc140/submissions/7411285
import sys
input = sys.stdin.readline

def main():
    n = int(input()[:-1])
    aa = list(map(int, input().split()))
    ans = 0
    pos = [0] * (n + 1)
    for i, a in enumerate(aa):
        pos[a] = i + 2
    Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
    Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
    for a in range(1,n + 1):
        i = pos[a]
        l0 = Lnext[i]
        l1 = Lnext[l0]
        r0 = Rnext[i]
        r1 = Rnext[r0]
        ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
        Lnext[r0] = l0
        Rnext[l0] = r0
    print(ans)

main()


from bisect import bisect_left
import array

n = int(input())
p = []

for i, x in enumerate(map(int, input().split())):
    p.append([x, i])

p.sort(reverse=True)

s = array.array('i', [-1, -1, p[0][1], n, n])

#print(p)

ans = 0
i = 2
for a, x in p[1:]:
    t = bisect_left(s, x)
    ans += a * ((x - s[t-1]) * (s[t+1] - s[t]) + (s[t] - x) * (s[t-1] - s[t-2]))
    #print(t, s)
    s.insert(t, x)
    i += 1


print(ans)




N = int(input())
P = list(map(int, input().split()))
R = list(range(N))
L = list(range(N))
I = [-1] * (N+1)
for i, p in enumerate(P):
    I[p] = i

ans = 0
for n, idx in enumerate(I[1:], 1):
    #print(f"n={n}, idx={idx}")
    l = idx-1
    while l>=0 and l!=L[l]:
        l = L[l]
    r = idx+1
    while r<N and r!=R[r]:
        r = R[r]
    L[idx] = l
    R[idx] = r

    if l != -1:
        l2 = l-1
        while l2>=0 and l2!=L[l2]:
            l2 = L[l2]
        #print(f"n * (l-l2) * (r-idx) = {n * (l-l2) * (r-idx)}")
        #print(l, l2)
        ans += n * (l-l2) * (r-idx)
        #L[l] = l2
    if r != N:
        r2 = r+1
        while r2<N and r2!=R[r2]:
            r2 = R[r2]
        #print(f"n * (idx-l) * (r2-r) = {n * (idx-l) * (r2-r)}")
        ans += n * (idx-l) * (r2-r)
        #R[r] = r2
print(ans)


# https://atcoder.jp/contests/abc140/submissions/7411285
# 写経

def main():
    N = int(input())
    *p, = list(map(int, input().split()))

    xtoi = [-1] * (N + 1)
    for i, x in enumerate(p):
        xtoi[x] = i

    L = [-1] * (N + 2)
    R = [N] * (N + 2)
    for i in range(N):
        L[i] = i - 1
        R[i] = i + 1

    iter_inds = iter(xtoi)
    next(iter_inds)

    ans = 0
    for x, ind in enumerate(iter_inds, start=1):
        # l2, ..., l1, ..., x, ..., r1, ..., r2
        # (l2,r1) or (l1,r2)
        l1 = L[ind]
        l2 = L[l1]
        r1 = R[ind]
        r2 = R[r1]
        ans += x * ((l1 - l2) * (r1 - ind) + (r2 - r1) * (ind - l1))
        L[r1] = l1
        R[l1] = r1
    print(ans)


def __starting_point():
    main()

__starting_point()

class Node:
    def __init__(self,  key=None):

        self.key = key
        self.height = 1
        self.parent = None
        self.left = None
        self.right = None


def update_height(t):
    if t.left is not None:
        l = t.left.height
    else:
        l = 0
    if t.right is not None:
        r = t.right.height
    else:
        r = 0
    
    if l >= r:
        t.height = l + 1
    else:
        t.height = r + 1


class AVL:
    def __init__(self):
        self.root = Node()       
    
    def insert(self, key):
        #値の挿入
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node

        #バランスの確認
        cursor = p
        while cursor:
            if cursor.left is not None:
                l = cursor.left.height
            else:
                l = 0
            if cursor.right is not None:
                r = cursor.right.height
            else:
                r = 0
            balance = l - r
            
            if balance == 0:
                break
            elif balance == 2:
                if key < cursor.left.key:
                    self.rotate_r(cursor)
                else:
                    self.rotate_lr(cursor)
                break
            elif balance == -2:
                if key > cursor.right.key:
                    self.rotate_l(cursor)
                else:
                    self.rotate_rl(cursor)
                break
            else:
                update_height(cursor)
                cursor = cursor.parent
           
    def rotate_r(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc is not None:
            n.left = gc
            gc.parent = n
        else:
            n.left = None
            
        c.right = n
        n.parent = c
        
        if p is not None:    
            if p.right == n:
                p.right = c
            else:
                p.left = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)
    
    def rotate_l(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc is not None:
            n.right = gc
            gc.parent = n
        else:
            n.right = None
            
        c.left = n
        n.parent = c
        
        if p is not None:
            if p.left == n:
                p.left = c
            else:
                p.right = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
        
        update_height(n)
        update_height(c)              
        
    def rotate_rl(self, n):
        
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc.left and gc.right:
            n.right = gc.left
            c.left = gc.right
            gc.left.parent = n
            gc.right.parent = c
        elif gc.left:
            n.right = gc.left
            gc.left.parent = n
            c.left = None
        elif gc.right:
            c.left = gc.right
            gc.right.parent = c
            n.right = None
        else:
            n.right = None
            c.left = None
            
        gc.left = n
        gc.right = c
        n.parent = gc
        c.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None

        update_height(n)
        update_height(c)
        update_height(gc)        
        
    def rotate_lr(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc.left and gc.right:
            c.right = gc.left
            n.left = gc.right
            gc.left.parent = c
            gc.right.parent = n
        elif gc.left:
            c.right = gc.left
            gc.left.parent = c
            n.left = None
        elif gc.right:
            n.left = gc.right
            gc.right.parent = n
            c.right = None
        else:
            n.left = None
            c.right = None
        gc.left = c
        gc.right = n
        c.parent = gc
        n.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)    
        
    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return None
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return None
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent              
        else:
            return None
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2


def main():

    N = int(input())
    P = map(int, input().split())
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
def __starting_point():
    main()
__starting_point()


n = int(input())
p = list(map(int,input().split()))

r = list(range(n))
l = list(range(n))
I = [-1] * (n+1)

for i,P in enumerate(p):
	I[P] = i
#I[1~Nまでの数字] = 0,1,...
#index を求めている
ans  = 0

for N,index in enumerate(I[1:],1):#1からスタート
	L = index -1
	if L >= 0:
		L = l[L]

	R = index + 1
	if  R < n:
		R = r[R]

	l[R-1] = L
	r[L+1] = R
#0 <= L , R < n
	if L >= 0:
		L2 = L-1
		if L2 >= 0:
			L2 = l[L2]
		ans += N * (L-L2) * (R - index)

	if R < n:
		R2 = R+1
		if R2 < n:
			R2 = r[R2]
		ans += N * (index - L ) * (R2 - R)
print(ans)


n=int(input())
p=list(map(int,input().split()))
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
d=[0]*(n+1)
for i in range(n):d[p[i]]=i+1
ans=0
for i in range(1,n+1):
  ans+=((r[r[d[i]]]-r[d[i]])*(d[i]-l[d[i]])+(r[d[i]]-d[i])*(l[d[i]]-l[l[d[i]]]))*i
  l[r[d[i]]],r[l[d[i]]]=l[d[i]],r[d[i]]
print(ans)

import sys
input=sys.stdin.readline
n=int(input())
a=[int(j) for j in input().split()]
ans=0
ind=[0]*(n+1)
for i in range(n):
    ind[a[i]]=i+1
l=[0]+list(range(n+1))
r=list(range(1,n+2))+[n+1]
for i in range(1,n+1):
    l1=l[ind[i]]
    l0=l[l1]
    r0=r[ind[i]]
    r1=r[r0]
    ans+=((l1-l0)*(r0-ind[i])+(r1-r0)*(ind[i]-l1))*i
    l[r0]=l1
    r[l1]=r0

print(ans)

import bisect

n=int(input())
p=[int(x)-1 for x in input().split()]

p2=sorted(enumerate(p), key=lambda x:x[1], reverse=True)  

ans=0
s=[-1,-1,n,n]
for i,(idx,p) in enumerate(p2):
  t=bisect.bisect_left(s,idx)
  s.insert(t,idx)
  l1=s[t-1]
  l2=s[t-2]
  r1=s[t+1]
  r2=s[t+2]
  ans+=(p+1)*((idx-l1)*(r2-r1)+(r1-idx)*(l1-l2))
              
print(ans)


from bisect import bisect_left, bisect_right, insort_right
class CubeSkipList:
    # SkipList の層数を 3 にした感じの何か
    # std::multiset の代用になる
    def __init__(self, values=None, sorted_=False, cube=100, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.cube = cube
        if values is None:
            self.layer2 = [inf]
            self.layer1 = [[]]
            self.layer0 = [[[]]]
        else:
            self.layer2 = layer2 = []
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l1 = []
            la0 = []
            l0 = []
            for v in values:
                r = rand_depth()
                if r==0:
                    l0.append(v)
                elif r==1:
                    la0.append(l0)
                    l0 = []
                    l1.append(v)
                else:
                    la0.append(l0)
                    layer0.append(la0)
                    layer1.append(l1)
                    l0 = []
                    la0 = []
                    l1 = []
                    layer2.append(v)
            la0.append(l0)
            layer0.append(la0)
            layer1.append(l1)
            layer2.append(inf)

    def rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        if y % self.cube == 0:
            if y % (self.cube ** 2) == 0:
                return 2
            return 1
        return 0

    def add(self, x):  # 要素の追加  # O(cbrt(n))
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        r = self.rand_depth()
        if r==0:
            idx2 = bisect_right(layer2, x)
            idx1 = bisect_right(layer1[idx2], x)
            insort_right(layer0[idx2][idx1], x)
        elif r==1:
            idx2 = bisect_right(layer2, x)
            l1 = layer1[idx2]
            idx1 = bisect_right(l1, x)
            l1.insert(idx1, x)
            la0 = layer0[idx2]
            l0 = la0[idx1]
            idx0 = bisect_right(l0, x)

            la0.insert(idx1+1, l0[idx0:])
            del l0[idx0:]
        else:
            idx2 = bisect_right(layer2, x)
            layer2.insert(idx2, x)
            l1 = layer1[idx2]
            idx1 = bisect_right(l1, x)
            la0 = layer0[idx2]
            l0 = la0[idx1]
            idx0 = bisect_right(l0, x)

            la0.insert(idx1+1, l0[idx0:])
            del l0[idx0:]
            layer0.insert(idx2+1, la0[idx1+1:])
            del la0[idx1+1:]
            layer1.insert(idx2+1, l1[idx1:])
            del l1[idx1:]

    def remove(self, x):  # 要素の削除  # O(cbrt(n))
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  # x 以上の最小の値を返す  O(log(n))
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        idx2 = bisect_right(layer2, x)
        l1 = layer1[idx2]
        idx1 = bisect_right(l1, x)
        la0 = layer0[idx2]
        l0 = la0[idx1]
        idx0 = bisect_right(l0, x)
        if idx0==len(l0):
            if idx1==len(l1):
                return layer2[idx2]
            return l1[idx1]
        return l0[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        idx2 = bisect_left(layer2, x)
        l1 = layer1[idx2]
        idx1 = bisect_left(l1, x)
        la0 = layer0[idx2]
        l0 = la0[idx1]
        idx0 = bisect_left(l0, x)
        if idx0==0:
            if idx1==0:
                return layer2[idx2-1]
            return l1[idx1-1]
        return l0[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め  使うなら square パラメータを大きめにするべき
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer2)
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = CubeSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

# 大きい数から挿入していく
# 左隣にあるインデックスを取得できるようにしておく
# そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ

# BITは一番最後の1ビットの位置が重要なので0ではなく1始まり。そのためNまでループする
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
    i = 0
    s = 0
    step = 1<<(N.bit_length()-1)
    while step:
        if i+step <= N and s + tree[i+step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i+1
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) # 左にある既に書き込んだ数の個数
    BIT_add(c)
    R = N-x-L # 右にある既に書き込んだ数の個数
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。(a,b) と(c,d)が自由
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)





N = int(input())
P = list(map(int, input().split()))

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

ans = 0
L = [i for i in range(-1, N-1)]
R = [i for i in range(1, N+1)]

for p in range(1,N+1):
    i = I[p-1]

    if R[i] < N:
        L[R[i]] = L[i]
    if L[i] >= 0:
        R[L[i]] = R[i]

    l1 = L[i]
    l2 = L[l1] if l1 >= 0 else -1
    r1 = R[i]
    r2 = R[r1] if r1 < N else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))

print(ans)


N = int(input())
P = list(map(int, input().split()))
R = list(range(N))
L = list(range(N))
I = [-1] * (N+1)
for i, p in enumerate(P):
    I[p] = i

ans = 0
for n, idx in enumerate(I[1:], 1):
    l = idx-1
    if l>=0:
        l = L[l]
    r = idx+1
    if r<N:
        r = R[r]
    L[r-1] = l
    R[l+1] = r

    if l>=0:
        l2 = l-1
        if l2>=0:
            l2 = L[l2]
        ans += n * (l-l2) * (r-idx)
    if r<N:
        r2 = r+1
        if r2<N:
            r2 = R[r2]
        ans += n * (idx-l) * (r2-r)
print(ans)


n=int(input())
p=list(map(int,input().split()))
l=[0]+[i for i in range(n+1)]#l_i...p_iよりも大きいもので、左側かつp_iに一番近い要素のindex
r=[i+1 for i in range(n+1)]+[n+1]#r_i...l_iの右側ver
d=[0]*(n+1)
for i in range(n):d[p[i]]=i+1
ans=0
for i in range(1,n+1):
  ans+=((r[r[d[i]]]-r[d[i]])*(d[i]-l[d[i]])+(r[d[i]]-d[i])*(l[d[i]]-l[l[d[i]]]))*i#l_iでで一番近い、l_(l_i)で二番目に近い(indexの差分取ってアレコレ計算)
  l[r[d[i]]],r[l[d[i]]]=l[d[i]],r[d[i]]#右側(左側)にある一番近いものを、自分を飛び越えて左側(右側)にくっつける(大小比較はしなくても良くて、どうせ後でまた更新される)
print(ans)

from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  # 要素の追加
        layer1, layer0 = self.layer1, self.layer0
        if self.rand_depth():
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if res != x:  # res > x
            if layer0_idx1:
                idx0 = bisect_left(layer0_idx1, x)
                if idx0 != 0:
                    return layer0_idx1[idx0-1]
            return layer1[idx1-1]  # layer0_idx1 が空の場合とすべて x 以上の場合
        else:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて res で埋まっている場合
                return layer1[idx1-1]
            else:
                return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))  for を回すので重め
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

N = int(input())
P = list(map(int,input().split()))

D = {P[i]:i+1 for i in range(N)}
ans = 0

L = SquareSkipList()
L.add(D[N])

for i in range(1,N)[::-1]:
    l = L.search_lower(D[i])
    h = L.search_higher(D[i])
    if l == float('inf'):
        hh = L.search_higher(h)
        if hh == float('inf'):
            hh = N+1
        ans += (D[i]*(hh-h))*i
    elif h == float('inf'):
        ll = L.search_lower(l)
        if ll == float('inf'):
            ll = 0
        ans += ((N+1-D[i])*(l-ll))*i
    else:
        hh = L.search_higher(h)
        if hh == float('inf'):
            hh = N+1
        ll = L.search_lower(l)
        if ll == float('inf'):
            ll = 0
        ans += ((h-D[i])*(l-ll)+(D[i]-l)*(hh-h))*i
    L.add(D[i])
    
print(ans)

# 勝てない つらい
# Python の bit 演算は遅い（本当に？）
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (add, pop) データ構造: https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (init, add, remove, search_higher_equal) Exclusive OR Queries: https://atcoder.jp/contests/cpsco2019-s1/submissions/7485749
    # 検証3 (add, search_higher, search_lower) Second Sum: https://atcoder.jp/contests/abc140/submissions/7485479
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= y << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0

        # xorshift
        y = self.rand_y
        #y ^= y << 13 & 0xffffffff
        #y ^= y >> 17
        #y ^= y << 5 & 0xffffffff
        y ^= y % 0x80000 * 0x2000
        y ^= y // 0x20000
        y ^= y % 0x8000000 * 0x20
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del layer1[idx1]
            layer0[idx1] += layer0.pop(idx1+1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    inf = float("inf")
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


# 勝てない つらい
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (データ構造): https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (Exclusive OR Queries): https://atcoder.jp/contests/cpsco2019-s1/submissions/7482199
    # 検証3 (Second Sum): https://atcoder.jp/contests/abc140/submissions/7482046
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0

        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        
        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め  使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    inf = float("inf")
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


# 勝てない つらい
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (add, pop) データ構造: https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (init, add, remove, search_higher_equal) Exclusive OR Queries: https://atcoder.jp/contests/cpsco2019-s1/submissions/7485446
    # 検証3 (add, search_higher, search_lower) Second Sum: https://atcoder.jp/contests/abc140/submissions/7483678
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y = self.rand_y
                y ^= y << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                self.rand_y = y
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0

        # xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del layer1[idx1]
            layer0[idx1] += layer0.pop(idx1+1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    inf = float("inf")
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


import heapq


N = int(input())

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


Llis = []
Rlis = []

for i in range(N):

    Llis.append([N,N])
    Rlis.append([N,N])
    P[i] -= 1


LQ1 = []
LQ2 = []

for i in range(N):

    while len(LQ2) > 0 and LQ2[0][0] < P[i]:
        Llis[LQ2[0][1]][1] = i
        heapq.heappop(LQ2)

    while len(LQ1) > 0 and LQ1[0][0] < P[i]:
        Llis[LQ1[0][1]][0] = i
        heapq.heappush(LQ2,LQ1[0])
        heapq.heappop(LQ1)

    heapq.heappush(LQ1,[P[i],i])

P.reverse()
LQ1 = []
LQ2 = []

for i in range(N):

    while len(LQ2) > 0 and LQ2[0][0] < P[i]:
        Rlis[LQ2[0][1]][1] = i
        heapq.heappop(LQ2)

    while len(LQ1) > 0 and LQ1[0][0] < P[i]:
        Rlis[LQ1[0][1]][0] = i
        heapq.heappush(LQ2,LQ1[0])
        heapq.heappop(LQ1)

    heapq.heappush(LQ1,[P[i],i])





Rlis.reverse()
#print (Llis,Rlis)

ans = 0
P.reverse()

for i in range(N):

    Llenge = Llis[i][1] - Llis[i][0]
    Rlenge = 1 + max(0,i - (N - Rlis[i][0]))

    ans += (P[i]+1) * Llenge * Rlenge
    #print (P[i] , Llenge , Rlenge)

P.reverse()
Rlis.reverse()
Llis.reverse()

for i in range(N):

    Rlenge = Rlis[i][1] - Rlis[i][0]
    Llenge = 1 + max(0,i - (N - Llis[i][0]))

    ans += (P[i]+1) * Llenge * Rlenge
    #print (P[i],Llenge,Rlenge)

print (ans)


    
        


n=int(input())
p=list(map(int,input().split()))
ind=[0]*n
for i in range(n):ind[p[i]-1]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(n):
  ans+=(r[r[ind[i]]]-r[ind[i]])*(ind[i]-l[ind[i]])*(i+1)
  ans+=(l[ind[i]]-l[l[ind[i]]])*(r[ind[i]]-ind[i])*(i+1)
  l[r[ind[i]]],r[l[ind[i]]]=l[ind[i]],r[ind[i]]
print(ans)

import bisect
n=int(input())
p=list(map(int,input().split()))
idx=[0]*(n+1)

for i,p_i in enumerate(p):
    idx[p_i]=i

right_idx=list(range(1,n+1))+[n,n]
left_idx =list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=idx[p]
    r1=right_idx[x]
    r2=right_idx[r1]
    l1=left_idx[x]
    l2=left_idx[l1]

    ans+=p*( (x-l1)*(r2-r1) + (l1-l2)*(r1-x)  )
    right_idx[l1]=r1
    left_idx[r1]=l1
print(ans)

from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (データ構造): https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (Exclusive OR Queries): https://atcoder.jp/contests/cpsco2019-s1/submissions/7482199
    # 検証3 (Second Sum): https://atcoder.jp/contests/abc140/submissions/7482046
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        if self.rand_depth():
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め  使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)



def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = TwoLayerSet(1/100)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()


import bisect


class BTreeNode:
    def __init__(self):
        self.key = []
        self.child = []


class BTree:
    def __init__(self):
        self.root = BTreeNode()

    def search_higher(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_right(ptr.key, key)
            if i != len(ptr.key):
                ret = ptr.key[i]
            ptr = ptr.child[i]
        i = bisect.bisect_right(ptr.key, key)
        if i != len(ptr.key):
            ret = ptr.key[i]
        return ret

    def search_lower(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_left(ptr.key, key)
            if i != 0:
                ret = ptr.key[i - 1]
            ptr = ptr.child[i]
        i = bisect.bisect_left(ptr.key, key)
        if i != 0:
            ret = ptr.key[i - 1]
        return ret

    def insert(self, key):
        def insert_rec(ptr):
            b_size = 512
            if not ptr.child:
                bisect.insort(ptr.key, key)
                if len(ptr.key) == b_size * 2 - 1:
                        ret = BTreeNode()
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            else:
                i = bisect.bisect(ptr.key, key)
                temp = insert_rec(ptr.child[i])
                if temp is not None:
                    ptr.key.insert(i, temp.key.pop(-1))
                    ptr.child.insert(i, temp)
                    if len(ptr.child) == b_size * 2:
                        ret = BTreeNode()
                        ret.child = ptr.child[:b_size]
                        ptr.child = ptr.child[b_size:]
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            return None
        temp = insert_rec(self.root)
        if temp is not None:
            root = BTreeNode()
            root.key = [temp.key.pop(-1)]
            root.child = [temp, self.root]
            self.root = root

    def dump(self):
        def dump_rec(ptr, dep):
            for _ in range(0, dep):
                print("  ", end="")
            print(ptr.key)
            for c in ptr.child:
                dump_rec(c, dep + 1)
        dump_rec(self.root, 0)
        print("")


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = BTree()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()


def f_e():
    n, *p = list(map(int, open(0).read().split()))
    p = sorted([(v, i) for i, v in enumerate(p)])
    *l, = list(range(-1, n-1))
    *r, = list(range(1, n+1))
    a = 0
    for v, i in p:
        l0, r0 = l[i], r[i]
        l1 = l[l0] if l0>-1 else l0
        r1 = r[r0] if r0<n else r0
        a += ((l0-l1)*(r0-i)+(r1-r0)*(i-l0))*v
        if l0>-1:
            r[l0]=r0
        if r0<n:
            l[r0]=l0
    print(a)

def __starting_point():
    f_e()

__starting_point()

class Node:
    def __init__(self, key=None):
        self.key = key
        self.balance = 'E'
        self.parent = None
        self.left = None
        self.right = None


class AVL:
    def __init__(self):
        self.root = Node()
        self.root.parent = Node('nil')

    def insert(self, key):
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node
            
        return self.rebalance(p, new_node, key)
            
    def rebalance(self, u, v, key):
        while u.key != 'nil':
            if u.key > v.key:
                if u.balance == 'R':
                    u.balance = 'E'
                    return
                elif u.balance == 'L':
                    if v.balance == 'L':
                        self.rotate_R(u, v)
                        return
                    elif v.balance == 'R':

                        self.rotate_LR(u, v)
                        return
                else:
                    u.balance = 'L'
                    v = u
                    u = u.parent
            else:
                if u.balance == 'L':
                    u.balance = 'E'
                    return
                elif u.balance == 'R':
                    if v.balance == 'R':
                        self.rotate_L(u, v)
                        return
                    elif v.balance == 'L':
                        self.rotate_RL(u, v)
                        return
                else:
                    u.balance = 'R'
                    v = u
                    u = u.parent
              
    def replace(self, u, v):
        if u.parent.left == u:
            u.parent.left = v
        else:
            u.parent.right = v
        v.parent = u.parent
        if v.parent.key == 'nil':
            self.root = v   

    def rotate_R(self, u, v):
        w = v.right

        self.replace(u, v)
        v.right = u
        u.parent = v        
        u.left = w        
        if w:
            w.parent = u
        u.balance = 'E'
        v.balance = 'E'           

    def rotate_L(self, u, v):
        w = v.left
        
        self.replace(u, v)
        v.left = u
        u.parent = v
        u.right = w        
        if w:
            w.parent = u
        u.balance = 'E'
        v.balance = 'E' 

    def rotate_LR(self, u, v):
        w = v.right
        
        self.replace(u, w)
        if w.left:
            v.right = w.left
            v.right.parent = v
        else:
            v.right = None
        if w.right:
            u.left = w.right
            u.left.parent = u
        else:
            u.left = None
        v.parent = w
        w.left = v
        u.parent = w
        w.right = u

        if w.balance == 'R':
            u.balance = 'E'
            v.balance = 'L'
        elif w.balance == 'L':
            u.balance ='R'
            v.balance = 'E'
        else:
            u.balance = 'E'
            v.balance = 'E'
        w.balance = 'E'        

    def rotate_RL(self, u, v):
        w = v.left
        
        self.replace(u, w)
        if w.left:
            w.left.parent = u
            u.right = w.left
        else:
            u.right = None
        if w.right:
            w.right.parent = v
            v.left = w.right
        else:
            v.left = None
        u.parent = w
        w.left = u
        v.parent = w
        w.right = v       
        
        if w.balance == 'R':
            u.balance = 'L'
            v.balance = 'E'
        elif w.balance == 'L':
            u.balance ='E'
            v.balance = 'R'
        else:
            u.balance = 'E'
            v.balance = 'E'
        w.balance = 'E'

    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent.key != 'nil' and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return 
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent.key != 'nil' and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2


def main():
#    import random
    import sys

#    N = 100000
#    P = list(range(1, N + 1))
#    random.shuffle(P)
    
    input = sys.stdin.readline
    N = int(input())
    P = map(int, input().split())    
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
def __starting_point():
    main()
__starting_point()

# 勝てない つらい seedで変わったりしませんか
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (add, pop) データ構造: https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (init, add, remove, search_higher_equal) Exclusive OR Queries: https://atcoder.jp/contests/cpsco2019-s1/submissions/7485446
    # 検証3 (add, search_higher, search_lower) Second Sum: https://atcoder.jp/contests/abc140/submissions/7483678
    def __init__(self, values=None, sorted_=False, square=1000, seed=1000000007):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y = self.rand_y
                y ^= y << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                self.rand_y = y
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0

        # xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del layer1[idx1]
            layer0[idx1] += layer0.pop(idx1+1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    inf = float("inf")
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


N = int(input())
P = [int(i) for i in input().split(" ")]

# 各数字が何番目に入っているかを保存する
pos = [0] * (N + 1)
for i in range(N):
    pos[P[i]] = i + 1

l = [0]+[i for i in range(N + 1)]
r = [i + 1 for i in range(N + 1)] + [N + 1]

# 1から順番に見ていく
ans = 0
for i in range(1, N + 1):
    idx = pos[i]
    l1, r1 = l[idx], r[idx]
    l2, r2 = l[l1], r[r1]
    ans += i * ((l1 - l2) * (r1 - idx) + (idx - l1) * (r2 - r1))
    l[r1], r[l1] = l1, r1
print(ans)

import bisect


class BTreeNode:
    def __init__(self):
        self.key = []
        self.child = []


class BTree:
    def __init__(self):
        self.root = BTreeNode()

    def search_higher(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_right(ptr.key, key)
            if i != len(ptr.key):
                ret = ptr.key[i]
            ptr = ptr.child[i]
        i = bisect.bisect_right(ptr.key, key)
        if i != len(ptr.key):
            ret = ptr.key[i]
        return ret

    def search_lower(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_left(ptr.key, key)
            if i != 0:
                ret = ptr.key[i - 1]
            ptr = ptr.child[i]
        i = bisect.bisect_left(ptr.key, key)
        if i != 0:
            ret = ptr.key[i - 1]
        return ret

    def insert(self, key):
        def insert_rec(ptr):
            b_size = 10
            if not ptr.child:
                bisect.insort(ptr.key, key)
                if len(ptr.key) == b_size * 2 - 1:
                        ret = BTreeNode()
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            else:
                i = bisect.bisect(ptr.key, key)
                temp = insert_rec(ptr.child[i])
                if temp is not None:
                    ptr.key.insert(i, temp.key.pop(-1))
                    ptr.child.insert(i, temp)
                    if len(ptr.child) == b_size * 2:
                        ret = BTreeNode()
                        ret.child = ptr.child[:b_size]
                        ptr.child = ptr.child[b_size:]
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            return None
        temp = insert_rec(self.root)
        if temp is not None:
            root = BTreeNode()
            root.key = [temp.key.pop(-1)]
            root.child = [temp, self.root]
            self.root = root

    def dump(self):
        def dump_rec(ptr, dep):
            for _ in range(0, dep):
                print("  ", end="")
            print(ptr.key)
            for c in ptr.child:
                dump_rec(c, dep + 1)
        dump_rec(self.root, 0)
        print("")


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = BTree()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()


# 勝てない つらい
# Python の bit 演算は遅い（本当に？）
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (add, pop) データ構造: https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (init, add, remove, search_higher_equal) Exclusive OR Queries: https://atcoder.jp/contests/cpsco2019-s1/submissions/7485749
    # 検証3 (add, search_higher, search_lower) Second Sum: https://atcoder.jp/contests/abc140/submissions/7485479
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= y << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0

        # xorshift
        y = self.rand_y
        #y ^= y << 13 & 0xffffffff
        #y ^= y >> 17
        #y ^= y << 5 & 0xffffffff
        y ^= (y & 0x7ffff) << 13
        y ^= y >> 17
        y ^= (y & 0x7ffffff) << 5
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del layer1[idx1]
            layer0[idx1] += layer0.pop(idx1+1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    inf = float("inf")
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

N = int(input())
Ps = list(map(int, input().split()))

iPs = [0] * (N+1)
for iP, A in enumerate(Ps):
    iPs[A] = iP

ans = 0
iLs = list(range(N+1))
iRs = list(range(N+1))
for P in range(1, N+1):
    i = iPs[P]
    iL, iR = iLs[i], iRs[i]
    if iL <= 1:
        iL2 = 0
    else:
        iL2 = iLs[iL-1]
    if iR >= N-2:
        iR2 = N-1
    else:
        iR2 = iRs[iR+1]
    num = 0
    if iL != 0:
        num += (iL-iL2)*(iR-i+1)
    if iR != N-1:
        num += (i-iL+1)*(iR2-iR)
    ans += P * num
    iLs[iR+1] = iL
    iRs[iL-1] = iR

print(ans)


from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (データ構造): https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (Exclusive OR Queries): https://atcoder.jp/contests/cpsco2019-s1/submissions/7482199
    # 検証3 (Second Sum): https://atcoder.jp/contests/abc140/submissions/7482046
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= y << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                if y % square:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
            layer1.append(inf)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0

        # xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め  使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    inf = float("inf")
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()


n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

N = int(input())
P = list(map(int, input().split()))
 
index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index
 
left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))
 
    left_next_Index[r1] = l1
    right_next_Index[l1] = r1
 
print (ans)

from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  # 要素の追加
        layer1, layer0 = self.layer1, self.layer0
        if self.rand_depth():
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if res != x:  # res > x
            if layer0_idx1:
                idx0 = bisect_left(layer0_idx1, x)
                if idx0 != 0:
                    return layer0_idx1[idx0-1]
            return layer1[idx1-1]  # layer0_idx1 が空の場合とすべて x 以上の場合
        else:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて res で埋まっている場合
                return layer1[idx1-1]
            else:
                return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        raise NotImplementedError  # 地味に実装が悩ましい

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)

main()


N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)

from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
sys.setrecursionlimit(100000)

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return list(map(int, input().split())) 
    else: return list(map(int, input().split(sep)))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    P = [N+1,N+1] + ria() + [N+1,N+1]

    ord = []
    for i in range(2,N+2):
        ord.append((P[i], i))

    ord = sorted(ord) # P[i], i , P[i]順でソート

    # ..AsssBssCssDsssE.. のようになっている（Cが自分 A,B,D,E>C，s<C）
    # CからA,B,D,Eのインデクスを知りたいので，Cより小さい区間は連結にして置き，
    # スキップできるように各連結成分の両端に情報を乗せておく
    #  union-findで管理してもいいが，アクセスする場所と回数が限られているので配列で管理できる
    tot = 0
    l = [i for i in range(N + 4)]
    r = [i for i in range(N + 4)]
    used = [False] * (N + 4)
    for v, idx in ord:
        # 左右がusedならマージする
        used[idx] = True
        if used[idx - 1]:
            l[idx] = l[idx - 1]
        if used[idx + 1]:
            r[idx] = r[idx + 1]
        r[l[idx]] = r[idx]
        l[r[idx]] = l[idx]

        l0 = l[idx] - 1
        r0 = r[idx] + 1
        l1 = l0 - 1 if not used[l0 - 1] else (l[l0-1] - 1)
        r1 = r0 + 1 if not used[r0 + 1] else (r[r0+1] + 1)
        #print(l1,l0,idx,r0,r1)

        if l1 != 0:
            rseg = r0 - idx
            lseg = l0 - l1
            tot += lseg * rseg * v
        if r1 != N + 3:
            rseg = r1 - r0
            lseg = idx - l0
            tot += lseg * rseg * v

    print(tot)




def __starting_point():
    main()

__starting_point()

from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = TwoLayerSet(1/50)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()


N = int(input())
P = [int(x) for x in input().split()]

PIdx = sorted([(i + 1, v) for i, v in enumerate(P)], key = lambda x: x[1])

L = [0]
for i in range(N + 1):
    L.append(i)

R = [i + 1 for i in range(N + 1)]
R.append(N + 1)

ans = 0
for i, v in PIdx:
    l1 = L[i]
    l2 = L[l1]
    r1 = R[i]
    r2 = R[r1]

    ans += v * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))

    L[r1] = l1
    R[l1] = r1

print(ans)