Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = [0]*n
    for i in range(n):
        l1[l[i]-1] = i
    ans = 0
    s = [-1,-1,l1[-1],n,n]

    for i in range(n-2,-1,-1):
        c = l1[i]
        now = bisect.bisect_right(s,c)
        a = s[now-2]
        b = s[now-1]
        d = s[now]
        e = s[now+1]
        count = (b-a)*(d-c) + (e-d)*(c-b)
        s.insert(now,c)
        ans += count*(i+1)
    print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = []
    for i in range(n):
        l1.append([l[i],i])
    l1.sort(reverse=True)
    ans = 0
    s = [-1,-1,l1[0][1],n,n]

    for i in range(1,n):
        c = l1[i][1]
        now = bisect.bisect_right(s,c)
        a = s[now-2]
        b = s[now-1]
        d = s[now]
        e = s[now+1]
        count = (b-a)*(d-c) + (e-d)*(c-b)
        s.insert(now,c)
        ans += count*(n-i)
    print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = []
    for i in range(n):
        l1.append([l[i],i])
    l1.sort(reverse=True)
    ans = 0
    s = [-1,-1,l1[0][1],n,n]

    for i in range(1,n):
        now = bisect.bisect_right(s,l1[i][1])
        count = (s[now-1]-s[now-2])*(s[now]-l1[i][1]) + (s[now+1]-s[now])*(l1[i][1]-s[now-1])
        s.insert(now,l1[i][1])
        ans += count*(n-i)
    print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = []
    for i in range(n):
        l1.append([l[i],i])
    l1.sort(reverse=True)
    ans = 0
    s = [-1,-1,l1[0][1],n,n]

    for i in range(1,n):
        now = bisect.bisect_right(s,l1[i][1])
        count = (s[now-1]-s[now-2])*(s[now]-l1[i][1]) + (s[now+1]-s[now])*(l1[i][1]-s[now-1])
        s.insert(now,l1[i][1])
        ans += count*(n-i)
    print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)