Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import math
import sys
input = sys.stdin.readline


def read_int():
    return int(input())

def read_int_n():
    return tuple(map(int, input().split()))


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            v = self.__f(
                self.__table[2*pi+1], self.__table[2*pi+2])
            if v != self.__table[pi]:
                self.__table[pi] = v
            else:
                break
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]

        ans = self.__ie
        while stack:
            k, l, r = stack.pop()
            if a <= l and r <= b:
                ans = self.__f(ans, self.__table[k])
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans

def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i+1) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        lst.update(i, i)
        l = lst.query(0, i)
        ll = lst.query(0, l) if l != 0 else 0

        rst.update(i, i)
        r = rst.query(i+1, N+2)
        rr = rst.query(r+1, N+2) if r != N+1 else N + 1

        c = 0
        c += (l-ll) * (r-i)
        c += (i-l) * (rr-r)

        ans += c*p

    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))



if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            v = self.__f(
                self.__table[2*pi+1], self.__table[2*pi+2])
            if v != self.__table[pi]:
                self.__table[pi] = v
            else:
                break
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]

        ans = self.__ie
        while stack:
            k, l, r = stack.pop()
            if a <= l and r <= b:
                ans = self.__f(ans, self.__table[k])
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans


@mt
def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i+1) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        lst.update(i, i)
        l = lst.query(0, i)
        ll = lst.query(0, l) if l != 0 else 0

        rst.update(i, i)
        r = rst.query(i+1, N+2)
        rr = rst.query(r+1, N+2) if r != N+1 else N + 1

        c = 0
        c += (l-ll) * (r-i)
        c += (i-l) * (rr-r)

        ans += c*p

    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))

    # N = 10**5
    # P = list(range(1, N+1))
    # random.shuffle(P)
    # print(N)
    # print(' '.join(map(str, P)))
    # # print(slv(N, P))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))



if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi] = self.__f(self.__table[pi], self.__table[i])
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]

        ans = self.__ie
        while stack:
            k, l, r = stack.pop()
            cnd = self.__table[k]
            if a <= l and r <= b:
                ans = self.__f(ans, cnd)
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))

        return ans


    def print(self):
        print(self.__table)

@mt
def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        i += 1

        lst.update(i, i)
        l = lst.query(0, i)
        if l != 0:
            ll = lst.query(0, l)
        else:
            ll = 0
        rst.update(i, i)
        r = rst.query(i+1, N+2)
        if r != N+1:
            rr = rst.query(r+1, N+2)
        else:
            rr = N + 1
        c = 0
        c += (l-ll) * (r - i)
        c += (i-l) * (rr - r)

        ans += c*p

    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))

    # N = 10**5
    # P = list(range(1, N+1))
    # random.shuffle(P)
    # print(slv(N, P))

if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))



if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi] = self.__f(self.__table[pi], self.__table[i])
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.__ie
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return self.__f(vl, vr)

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        i += 1

        lst.update(i, i)
        l = lst.query(0, i)
        if l != 0:
            ll = lst.query(0, l)
        else:
            ll = 0
        rst.update(i, i)
        r = rst.query(i+1, N+2)
        if r != N+1:
            rr = rst.query(r+1, N+2)
        else:
            rr = N + 1
        c = 0
        c += (l-ll) * (r - i)
        c += (i-l) * (rr - r)

        ans += c*p

    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))

    # N = 10**5
    # P = list(range(1, N+1))
    # random.shuffle(P)
    # print(slv(N, P))

if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))



if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi] = self.__f(self.__table[pi], self.__table[i])
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.__ie
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return self.__f(vl, vr)

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)

def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        i += 1

        lst.update(i, i)
        l = lst.query(0, i)
        if l != 0:
            ll = lst.query(0, l)
        else:
            ll = 0
        rst.update(i, i)
        r = rst.query(i+1, N+2)
        if r != N+1:
            rr = rst.query(r+1, N+2)
        else:
            rr = N + 1
        c = 0
        c += (l-ll) * (r - i)
        c += (i-l) * (rr - r)

        ans += c*p

    return ans



def slv3(N, P):
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)
    done = [0, N+1]
    ans = 0
    for p, i in P2:
        i += 1
        j = bisect.bisect(done, i)
        bisect.insort(done, i)
        c = 0
        if j >= 2:
            l = done[j-1] - done[j-2]
            r = done[j+1] - done[j]
            c += l * r
        if j <= len(done) - 3:
            l = done[j] - done[j-1]
            r = done[j+2] - done[j+1]
            c += l*r
        ans += c*p

    return ans


@mt
def slv2(N, P):
    ans = 0
    c = Counter()
    for i, j in combinations(range(N), 2):
        a = sorted(P[i:j+1], reverse=True)[1]
        ans += a
        c[a] += 1
    print(c)
    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))
    # print(slv2(N, P))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))



if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(N, P):
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)
    done = [0, N+1]
    ans = 0
    for p, i in P2:
        i += 1
        j = bisect.bisect(done, i)
        bisect.insort(done, i)
        c = 0
        if j >= 2:
            l = done[j-1] - done[j-2]
            r = done[j+1] - done[j]
            c += l * r
        if j <= len(done) - 3:
            l = done[j] - done[j-1]
            r = done[j+2] - done[j+1]
            c += l*r
        ans += c*p
        
    return ans


@mt
def slv2(N, P):
    ans = 0
    c = Counter()
    for i, j in combinations(range(N), 2):
        a = sorted(P[i:j+1], reverse=True)[1]
        ans += a
        c[a] += 1
    print(c)
    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))
    # print(slv2(N, P))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))



if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(N, P):
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)
    done = [0, N+1]
    ans = 0
    for p, i in P2:
        i += 1
        j = bisect.bisect(done, i)
        bisect.insort(done, i)
        c = 0
        if j >= 2:
            l = done[j-1] - done[j-2]
            r = done[j+1] - done[j]
            c += l * r
        if j <= len(done) - 3:
            l = done[j] - done[j-1]
            r = done[j+2] - done[j+1]
            c += l*r
        ans += c*p
        
    return ans


@mt
def slv2(N, P):
    ans = 0
    c = Counter()
    for i, j in combinations(range(N), 2):
        a = sorted(P[i:j+1], reverse=True)[1]
        ans += a
        c[a] += 1
    print(c)
    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))
    # print(slv2(N, P))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))



if __name__ == '__main__':
    main()