Buggy python submission (verdict: Runtime Error):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = deque([0, 0, num + 1, num + 1])
    # ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        # bisect.insort_left(ind_list, ori_ind)
        # add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = -1
        ind_list.insert(add_ind, ori_ind)
        # print(add_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()



Fixed submission:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        # bisect.insort_left(ind_list, ori_ind)
        # add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        ind_list.insert(add_ind, ori_ind)
        # print(add_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()



Fixed submission:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        # bisect.insort_left(ind_list, ori_ind)
        # add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        ind_list.insert(add_ind, ori_ind)
        # print(add_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()



Fixed submission:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        bisect.insort_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()



Fixed submission:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


if __name__ == '__main__':
    main()