Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getSize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
A = [0] + list(map(int, input().split())) + [N+1]
B = [None] * (N+2)
for i, x in enumerate(A):
    B[x] = i
A[0] = N+1
uf = UnionFind(N+1)
ans = 0
for x in range(1, N):
    i = B[x]
    if A[i-1] < A[i]:
        uf.unite(i-1, i)
    if A[i] > A[i+1]:
        uf.unite(i, i+1)
    if x < A[i-1]:
        k2 = i-1
    else:
        l, r = 0, i-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, i-1):
                r = m
            else:
                l = m
        k2 = l
    if k2 == 0 or A[max(0, k2-1)] > x:
        k1 = max(0, k2-1)
    else:
        l, r = 0, k2-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, k2-1):
                r = m
            else:
                l = m
        k1 = l
    if x < A[i+1]:
        k3 = i+1
    else:
        l, r = i+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(i+1, m):
                l = m
            else:
                r = m
        k3 = r
    if k3 == N+1 or x < A[min(N+1, k3+1)]:
        k4 = min(N+1, k3+1)
    else:
        l, r = k3+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(k3+1, m):
                l = m
            else:
                r = m
        k4 = r
    ans += x * ((k2-k1)*(k3-i) + (k4-k3)*(i-k2))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getSize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
A = [0] + list(map(int, input().split())) + [N+1]
B = [None] * (N+2)
for i, x in enumerate(A):
    B[x] = i
A[0] = N+1
uf = UnionFind(N+1)
ans = 0
for x in range(1, N):
    i = B[x]
    if A[i-1] < A[i]:
        uf.unite(i-1, i)
    if A[i] > A[i+1]:
        uf.unite(i, i+1)
    if x < A[i-1]:
        k2 = i-1
    else:
        l, r = 0, i-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, i-1):
                r = m
            else:
                l = m
        k2 = l
    if k2 == 0 or A[max(0, k2-1)] > x:
        k1 = max(0, k2-1)
    else:
        l, r = 0, k2-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, k2-1):
                r = m
            else:
                l = m
        k1 = l
    if x < A[i+1]:
        k3 = i+1
    else:
        l, r = i+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(i+1, m):
                l = m
            else:
                r = m
        k3 = r
    if k3 == N+1 or x < A[min(N+1, k3+1)]:
        k4 = min(N+1, k3+1)
    else:
        l, r = k3+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(k3+1, m):
                l = m
            else:
                r = m
        k4 = r
    ans += x * ((k2-k1)*(k3-i) + (k4-k3)*(i-k2))
print(ans)