#!/usr/bin/env python3

N=int(eval(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)

#!/usr/bin/env python3

ans=0

n=int(eval(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)

#!/usr/bin/env python3
N = int(eval(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)

#!/usr/bin/env python3
ans = 0
n = int(eval(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)

-N = int(eval(input())) +ans = 0 +n = int(eval(input())) -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] +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]] -    l0 = LL[i] -    l1 = LL[l0] -    RR[l0] = r0 -    LL[r0] = l0 -    ans += ((r1 - r0) * (i - l0) + (r0 - i) * (l0 - l1)) * v +    ans += ((l1 - l0) * (r0 - b[i]) + (r1 - r0) * (b[i] - l1)) * i +    LL[r0] = l1 +    RR[l1] = r0