Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
P = []
for i, p in enumerate(map(int, input().split())):
    P.append([p, i])

P = sorted(P, reverse = True)
    
A = [- 1, - 1, P[0][1], N, N] 

res = 0
for p, i in P[1:]:
    j = bisect.bisect_left(A, i)
    A.insert(j, i)
    res += p*((A[j] - A[j - 1])*(A[j + 2] - A[j + 1]) + (A[j - 1] - A[j - 2])*(A[j + 1] - A[j]))

print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
P_id = [0]*(N + 1)
for i, p in enumerate(map(int, input().split())):
    P_id[p] = i
    
A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
P = map(int, input().split())
P_id = [0]*(N + 1)

i = 0
for p in P:
    P_id[p] = i
    i += 1
    
A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
    
print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Runtime Error):
import bisect
N = int(input())
P = map(int, input().split())
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, - 1, P_id[N], N, N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l2, l1 = A[j - 2 : j]
    r1, r2 = A[j + 1: j + 3]
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
    
print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    a = A[j]
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(a + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - a)
    else:
        res += i*((a - l1)*(r2 - r1) + (l1 - l2)*(r1 - a))
print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(A[j] + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - A[j])
    else:
        res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
def search_index(x, sorted_ls):
    '''
    ソート済み配列からxの入る位置を返す and sorted_lsにxを挿入。
    xの入る位置が複数ある場合は一番左のindexを返す。
    '''
    n = len(sorted_ls)
    l = 0
    r = n
    while l != r:
        a = (r + l)//2
        if x <= sorted_ls[a]:
            r = a
        else:
            l = a + 1
    sorted_ls.insert(l, x)
    return l


N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = search_index(P_id[i], A)
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(A[j] + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - A[j])
    else:
        res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))
res = 0
for i in range(N):
    if P[i] == N:
        continue
    l1 = i - 1
    r1 =  i + 1
    while l1 >= 0 and P[l1] < P[i]:
        l1 -= 1
    while r1 < N and P[r1] < P[i]:
        r1 += 1
    l2 = l1 - 1
    r2 = r1 + 1
    while l2 >= 0 and P[l2] < P[i]:
        l2 -= 1
    while r2 < N and P[r2] < P[i]:
        r2 += 1
    if l1 == - 1:
        res += P[i]*(i + 1)*(r2 - r1)
    elif r1 == N:
        res += P[i]*(l1 - l2)*(N - i)
    else:
        res += P[i]*((l1 - l2)*(r1 - i) + (i - l1)*(r2 - r1))
print(res)

Fixed submission:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)