Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input=sys.stdin.readline
    from bisect import bisect,insort
    n=int(input())
    p=list(map(int,input().split()))
    p=[0]+p
    q=[0]*(n+1)
    for i in range(1,n+1):
        q[p[i]]=i
    lst=[0,q[n],n+1]
    ans=0
    for i in range(1,n):
        k=i
        i=n-i
        num=q[i]
        a=bisect(lst,num)
        if a==1:
            ans+=i*num*(lst[2]-lst[1])
            insort(lst,num)
        elif a==1+k:
            ans+=i*(n+1-num)*(lst[k]-lst[k-1])
            insort(lst,num)
        else:
            b=lst[a-2]
            c=lst[a-1]
            d=lst[a]
            e=lst[a+1]
            ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
            insort(lst,num)
    print(ans)
if __name__=="__main__":
    main()

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input=sys.stdin.readline
    from bisect import bisect,insort
    n=int(input())
    p=list(map(int,input().split()))
    p=[0]+p
    q=[0]*(n+1)
    for i in range(1,n+1):
        q[p[i]]=i
    lst=[0,q[n],n+1]
    ans=0
    for i in range(1,n):
        k=i
        i=n-i
        num=q[i]
        a=bisect(lst,num)
        if a==1:
            ans+=i*num*(lst[2]-lst[1])
            insort(lst,num)
        elif a==1+k:
            ans+=i*(n+1-num)*(lst[k]-lst[k-1])
            insort(lst,num)
        else:
            b=lst[a-2]
            c=lst[a-1]
            d=lst[a]
            e=lst[a+1]
            ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
            insort(lst,num)
    print(ans)
if __name__=="__main__":
    main()

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect,insort
n=int(input())
p=list(map(int,input().split()))
p=[0]+p
q=[0]*(n+1)
for i in range(1,n+1):
    q[p[i]]=i
lst=[0,q[n],n+1]
ans=0
for i in range(1,n):
    k=i
    i=n-i
    num=q[i]
    a=bisect(lst,num)
    if a==1:
        ans+=i*num*(lst[2]-lst[1])
        insort(lst,num)
    elif a==1+k:
        ans+=i*(n+1-num)*(lst[k]-lst[k-1])
        insort(lst,num)
    else:
        b=lst[a-2]
        c=lst[a-1]
        d=lst[a]
        e=lst[a+1]
        ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
        insort(lst,num)
print(ans)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect,insort
n=int(input())
p=list(map(int,input().split()))
p=[0]+p
q=[0]*(n+1)
for i in range(1,n+1):
    q[p[i]]=i
lst=[0,q[n],n+1]
ans=0
for i in range(1,n):
    k=i
    i=n-i
    num=q[i]
    a=bisect(lst,num)
    if a==1:
        ans+=i*num*(lst[2]-lst[1])
        insort(lst,num)
    elif a==1+k:
        ans+=i*(n+1-num)*(lst[k]-lst[k-1])
        insort(lst,num)
    else:
        b=lst[a-2]
        c=lst[a-1]
        d=lst[a]
        e=lst[a+1]
        ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
        insort(lst,num)
print(ans)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
p=[0]+p
q=[0]*(n+1)
for i in range(1,n+1):
    q[p[i]]=i
lst=[0,q[n],n+1]
ans=0
for i in range(1,n):
    k=i
    i=n-i
    num=q[i]
    a=bisect(lst,num)
    if a==1:
        ans+=i*num*(lst[2]-lst[1])
        lst=[0,num]+lst[1:]
    elif a==1+k:
        ans+=i*(n+1-num)*(lst[k]-lst[k-1])
        lst=lst[:1+k]+[num,n+1]
    else:
        b=lst[a-2]
        c=lst[a-1]
        d=lst[a]
        e=lst[a+1]
        ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
        lst=lst[:a]+[num]+lst[a:]
print(ans)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n):
    data[p[i]]=i+1
lst=[data[n]]
ans=0
if data[n-1]>data[n]:
    lst.append(data[n-1])
    a=lst[0]*(n-lst[1]+1)
    ans+=a*(n-1)
else:
    lst=[data[n-1]]+lst
    a=lst[0]*(n-lst[1]+1)
    ans+=a*(n-1)
lst.append(n+1)
lst=[0]+lst
for i in range(2,n):
    h=data[n-i]
    y=bisect(lst,h)
    L=len(lst)
    if y==1:
        a=h*(lst[2]-lst[1])
        ans+=a*(n-i)
        lst=[lst[0]]+[h]+lst[1:]
    elif y==L-1:
        a=(n-h+1)*(lst[-2]-lst[-3])
        ans+=a*(n-i)
        lst=lst[:(L-1)]+[h]+[lst[-1]]
    else:
        a=(lst[y+1]-lst[y])*(h-lst[y-1])+(lst[y]-h)*(lst[y-1]-lst[y-2])
        ans+=a*(n-i)
        lst=lst[:y]+[h]+lst[y:]
print(ans)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n):
    data[p[i]]=i+1
lst=[data[n]]
ans=0
if data[n-1]>data[n]:
    lst.append(data[n-1])
    a=lst[0]*(n-lst[1]+1)
    ans+=a*(n-1)
else:
    lst=[data[n-1]]+lst
    a=lst[0]*(n-lst[1]+1)
    ans+=a*(n-1)
lst.append(n+1)
lst=[0]+lst
for i in range(2,n):
    h=data[n-i]
    y=bisect(lst,h)
    L=len(lst)
    if y==1:
        a=h*(lst[2]-lst[1])
        ans+=a*(n-i)
        lst=[lst[0]]+[h]+lst[1:]
    elif y==L-1:
        a=(n-h+1)*(lst[-2]-lst[-3])
        ans+=a*(n-i)
        lst=lst[:(L-1)]+[h]+[lst[-1]]
    else:
        a=(lst[y+1]-lst[y])*(h-lst[y-1])+(lst[y]-h)*(lst[y-1]-lst[y-2])
        ans+=a*(n-i)
        lst=lst[:y]+[h]+lst[y:]
print(ans)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n):
    data[p[i]]=i+1
lst=[data[n]]
ans=0
if data[n-1]>data[n]:
    lst.append(data[n-1])
    ans+=(lst[0]*(n-lst[1]+1))*(n-1)
else:
    lst=[data[n-1]]+lst
    ans+=(lst[0]*(n-lst[1]+1))*(n-1)
lst.append(n+1)
lst=[0]+lst
for i in range(2,n):
    h=data[n-i]
    y=bisect(lst,h)
    if y==1:
        ans+=(h*(lst[2]-lst[1]))*(n-i)
        lst=[lst[0]]+[h]+lst[1:]
    elif y==len(lst)-1:
        ans+=((n-h+1)*(lst[-2]-lst[-3]))*(n-i)
        lst=lst[:(len(lst)-1)]+[h]+[lst[-1]]
    else:
        ans+=((lst[y+1]-lst[y])*(h-lst[y-1])+(lst[y]-h)*(lst[y-1]-lst[y-2]))*(n-i)
        lst=lst[:y]+[h]+lst[y:]
print(ans)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)