Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    P = [None] + list(map(int, input().split()))

    p_to_index = [None] * (N + 1)
    for index, x in enumerate(P[1:], 1):
        p_to_index[x] = index

    #大きい数から挿入
    #左隣にあるインデックスを取得できるようにする
    #[1, i]内で書き込んだ数の個数を獲得できるBITを構築する

    def BIT_add(i):
        while i <= N:
            tree[i] += 1
            i += i & (-i)

    def BIT_sum(i):
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def BIT_search(x):
        i = 0
        s = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and s + tree[i + step] < x:
                i += step
                s += tree[i]
            step >>= 1
        return i + 1

    tree = [0] * (N + 1)
    ans = 0
    for x in range(N, 0, -1):
        c = p_to_index[x]
        L = BIT_sum(c) #左側にある既に書き込んだ数の個数
        BIT_add(c)
        R = N - x - L #右側にある既に書き込んだ数の個数
        a = BIT_search(L - 1) if L >= 2 else 0
        b = BIT_search(L) if L >= 1 else 0
        d = BIT_search(L + 2) if R >= 1 else N + 1
        e = BIT_search(L + 3) if R >= 2 else N + 1
        if b != 0:
            ans += x * (b - a) * (d - c)
        if d != 0:
            ans += x * (e - d) * (c - b)

    print (ans)

if __name__ == '__main__':
    main()

Fixed submission:
N = int(input())
P = list(map(int, input().split()))

index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index

left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
# print (left_next_Index)
# print (right_next_Index)
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))

    left_next_Index[r1] = l1
    right_next_Index[l1] = r1

print (ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
P = [None] + list(map(int, input().split()))

p_to_index = [None] * (N + 1)
for index, x in enumerate(P[1:], 1):
    p_to_index[x] = index

#大きい数から挿入
#左隣にあるインデックスを取得できるようにする
#[1, i]内で書き込んだ数の個数を獲得できるBITを構築する

def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i & (-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i & (-i)
    return s

def BIT_search(x):
    i = 0
    s = 0
    step = 1 << (N.bit_length() - 1)
    while step:
        if i + step <= N and s + tree[i + step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i + 1

tree = [0] * (N + 1)
ans = 0
for x in range(N, 0, -1):
    c = p_to_index[x]
    L = BIT_sum(c) #左側にある既に書き込んだ数の個数
    BIT_add(c)
    R = N - x - L #右側にある既に書き込んだ数の個数
    a = BIT_search(L - 1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L + 2) if R >= 1 else N + 1
    e = BIT_search(L + 3) if R >= 2 else N + 1
    tmp = 0
    if b != 0:
        tmp += (b - a) * (d - c)
    if d != 0:
        tmp += (e - d) * (c - b)
    ans += tmp * x

print (ans)


Fixed submission:
N = int(input())
P = list(map(int, input().split()))

index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index

left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
# print (left_next_Index)
# print (right_next_Index)
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))

    left_next_Index[r1] = l1
    right_next_Index[l1] = r1

print (ans)

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

p_to_index = [None] * (N + 1)
for index, x in enumerate(P[1:], 1):
    p_to_index[x] = index

#大きい数から挿入
#左隣にあるインデックスを取得できるようにする
#[1, i]内で書き込んだ数の個数を獲得できるBITを構築する

def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i & (-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i & (-i)
    return s

def BIT_search(x):
    i = 0
    s = 0
    step = 1 << (N.bit_length() - 1)
    while step:
        if i + step <= N and s + tree[i + step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i + 1

tree = [0] * (N + 1)
ans = 0
for x in range(N, 0, -1):
    c = p_to_index[x]
    L = BIT_sum(c) #左側にある既に書き込んだ数の個数
    BIT_add(c)
    R = N - x - L #右側にある既に書き込んだ数の個数
    a = BIT_search(L - 1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L + 2) if R >= 1 else N + 1
    e = BIT_search(L + 3) if R >= 2 else N + 1
    tmp = 0
    if b != 0:
        tmp += (b - a) * (d - c)
    if d != 0:
        tmp += (e - d) * (c - b)
    ans += tmp * x

print (ans)


Fixed submission:
N = int(input())
P = list(map(int, input().split()))

index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index

left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
# print (left_next_Index)
# print (right_next_Index)
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))

    left_next_Index[r1] = l1
    right_next_Index[l1] = r1

print (ans)