Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
import sys


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, sys.stdin.readline().rstrip().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
ans = 0
for i,p in Pn[1:]:
  cnt = 0
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    cnt += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    cnt += l*r
  ans += cnt*p

print(ans)

Fixed submission:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



N = int(input())
Pn = list(map(int, input().split()))

In = [0] * (N+1)
for i in range(N):
  In[Pn[i]] = i+1

cnt = 0
l = [0] + [i for i in range(N+1)]
r = [i+1 for i in range((N+1))] + [N+1]

for v in range(1, N+1):
  i = In[v]
  
  l1 = l[i]
  l2 = l[l1]
  r1 = r[i]
  r2 = r[r1]
  cnt += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * v
  
  l[r1] = l1
  r[l1] = r1
    
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
import sys


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, sys.stdin.readline().rstrip().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
ans = 0
for i,p in Pn[1:]:
  cnt = 0
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    cnt += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    cnt += l*r
  ans += cnt*p

print(ans)

Fixed submission:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



N = int(input())
Pn = list(map(int, input().split()))

In = [0] * (N+1)
for i in range(N):
  In[Pn[i]] = i+1

cnt = 0
l = [0] + [i for i in range(N+1)]
r = [i+1 for i in range((N+1))] + [N+1]

for v in range(1, N+1):
  i = In[v]
  
  l1 = l[i]
  l2 = l[l1]
  r1 = r[i]
  r2 = r[r1]
  cnt += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * v
  
  l[r1] = l1
  r[l1] = r1
    
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, input().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
ans = 0
for i,p in Pn[1:]:
  cnt = 0
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    cnt += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    cnt += l*r
  ans += cnt*p

print(ans)

Fixed submission:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



N = int(input())
Pn = list(map(int, input().split()))

In = [0] * (N+1)
for i in range(N):
  In[Pn[i]] = i+1

cnt = 0
l = [0] + [i for i in range(N+1)]
r = [i+1 for i in range((N+1))] + [N+1]

for v in range(1, N+1):
  i = In[v]
  
  l1 = l[i]
  l2 = l[l1]
  r1 = r[i]
  r2 = r[r1]
  cnt += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * v
  
  l[r1] = l1
  r[l1] = r1
    
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, input().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
Cn = [0 for _ in range(N+1)]
for i,p in Pn[1:]:
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    Cn[p] += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    Cn[p] += l*r

ans = 0
for i,c in enumerate(Cn):
  ans += i*c
print(ans)

Fixed submission:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



N = int(input())
Pn = list(map(int, input().split()))

In = [0] * (N+1)
for i in range(N):
  In[Pn[i]] = i+1

cnt = 0
l = [0] + [i for i in range(N+1)]
r = [i+1 for i in range((N+1))] + [N+1]

for v in range(1, N+1):
  i = In[v]
  
  l1 = l[i]
  l2 = l[l1]
  r1 = r[i]
  r2 = r[r1]
  cnt += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * v
  
  l[r1] = l1
  r[l1] = r1
    
print(cnt)