Buggy python submission (verdict: Time Limit Exceeded):
class LazySegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        LV = (A - 1).bit_length()
        n = 2 ** LV
        self.__LV = LV
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        self.__lazy = [None] * (2 * n)
        # for i in range(len(A)):
        #     self.__node[i + n] = A[i]
        # for i in range(n - 1, 0, -1):
        #     self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def gindex(self, l, r):
        L = (l + self.__n) >> 1
        R = (r + self.__n) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.__LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    def propagates(self, *ids):
        lazy = self.__lazy
        node = self.__node
        for i in reversed(ids):
            v = lazy[i]
            if v is None:
                continue
            lazy[2 * i] = node[2 * i] = lazy[2 * i + 1] = node[2 * i + 1] = v
            lazy[i] = None
            
    def update(self, l, r, x):
        """
        区間[l, r)をxで更新
        """
        # i += self.__n
        # node = self.__node
        # node[i] = c
        # while i > 0:
        #     i //= 2
        #     node[i] = self.__dot(node[2 * i], node[2 * i + 1])
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        L = l + self.__n; R = r + self.__n
        lazy = self.__lazy
        node = self.__node
        while L < R:
            if R & 1:
                R -= 1
                lazy[R] = node[R] = x
            if L & 1:
                lazy[L] = node[L] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        self.propagates(*self.gindex(l, r))
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = LazySegmentTree(N, max, -1)
    minSeg = LazySegmentTree(N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c + 1, c)
        minSeg.update(c, c + 1, c)

    print(cnt)


solve()


Fixed submission:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        # for i in range(len(A)):
        #     self.__node[i + n] = A[i]
        # for i in range(n - 1, 0, -1):
        #     self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree([-1] * N, max, -1)
    minSeg = SegmentTree([N] * N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))

leftMax = [0] * N
rightMax = [0] * N
leftMax[0] = P[0]
rightMax[-1] = P[-1]
for i in range(N - 1):
    leftMax[i + 1] = max(leftMax[i], P[i + 1])
    rightMax[N - 1 - (i + 1)] = max(rightMax[N - 1 - i], P[N - 1 - i])

ans = 0
for i in range(N):
    a, b, c, d = -1, -1, N, N
    p = P[i]
    if leftMax[i] != p:
        for L in range(i - 1, -1, -1):
            if P[L] > p:
                if b == -1:
                    b = L
                elif a == -1:
                    a = L
                else:
                    break
    if rightMax[i] != p:
        for R in range(i + 1, N):
            if P[R] > p:
                if c == N:
                    c = R
                elif d == N:
                    d = R
                else:
                    break
    left = (b - a) * (c - i)
    right = (d - c) * (i - b)
    ans += p * (left + right)

print(ans)


Fixed submission:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        # for i in range(len(A)):
        #     self.__node[i + n] = A[i]
        # for i in range(n - 1, 0, -1):
        #     self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree([-1] * N, max, -1)
    minSeg = SegmentTree([N] * N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))


ans = 0
for i in range(N):
    a, b, c, d = -1, -1, N, N
    for L in range(i - 1, -1, -1):
        if P[L] > P[i]:
            if b == -1:
                b = L
            elif a == -1:
                a = L
            else:
                break
    for R in range(i + 1, N):
        if P[R] > P[i]:
            if c == N:
                c = R
            elif d == N:
                d = R
            else:
                break
    left = (b - a) * (c - i)
    right = (d - c) * (i - b)
    ans += P[i] * (left + right)

print(ans)


Fixed submission:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        # for i in range(len(A)):
        #     self.__node[i + n] = A[i]
        # for i in range(n - 1, 0, -1):
        #     self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree([-1] * N, max, -1)
    minSeg = SegmentTree([N] * N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()