Buggy python submission (verdict: Time Limit Exceeded):
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.append(i)
        I.sort()
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.insert(j, i)
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = Q.index(c)
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.append(i)
        I.sort()
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.insert(j, i)
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = Q.index(c)
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.append(i)
        I.sort()
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.insert(j, i)
    print(ans)


if __name__ == '__main__':
    main()