import bisect

import array

N = int(eval(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)
N = int(eval(input()))

P_id = [0]*(N + 1) # P_id[i]は順列Pに置けるiのindex, P[0]は無視

for index, p in enumerate(map(int, input().split())):

    P_id[p] = index



left_next_index = list(range(- 1, N - 1)) + ['うんこ', - 1] # + [- 1]ではないことに注意, left_next_index[r1] = l1においてr1 = Nの場合があるから

right_next_index = list(range(1, N + 1)) + [N, 'うんこ']



res = 0

for p in range(1, N):

    l1 = left_next_index[P_id[p]]

    l2 = left_next_index[l1]

    r1 = right_next_index[P_id[p]]

    r2 = right_next_index[r1]

    

    res += p*((l1 - l2)*(r1 - P_id[p]) + (P_id[p] - l1)*(r2 - r1))

    

    left_next_index[r1] = l1

    right_next_index[l1] = r1

    

print(res)
import bisect
import array

N = int(eval(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)

N = int(eval(input()))
P_id = [0] * (N + 1)  # P_id[i]は順列Pに置けるiのindex, P[0]は無視
for index, p in enumerate(map(int, input().split())):
    P_id[p] = index
left_next_index = list(range(-1, N - 1)) + [
    "うんこ",
    -1,
]  # + [- 1]ではないことに注意, left_next_index[r1] = l1においてr1 = Nの場合があるから
right_next_index = list(range(1, N + 1)) + [N, "うんこ"]
res = 0
for p in range(1, N):
    l1 = left_next_index[P_id[p]]
    l2 = left_next_index[l1]
    r1 = right_next_index[P_id[p]]
    r2 = right_next_index[r1]
    res += p * ((l1 - l2) * (r1 - P_id[p]) + (P_id[p] - l1) * (r2 - r1))
    left_next_index[r1] = l1
    right_next_index[l1] = r1
print(res)

-import bisect -import array - -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]) +P_id = [0] * (N + 1)  # P_id[i]は順列Pに置けるiのindex, P[0]は無視 +for index, p in enumerate(map(int, input().split())): +    P_id[p] = index +left_next_index = list(range(-1, N - 1)) + [ +    "うんこ", +    -1, +]  # + [- 1]ではないことに注意, left_next_index[r1] = l1においてr1 = Nの場合があるから +right_next_index = list(range(1, N + 1)) + [N, "うんこ"] -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])) +for p in range(1, N): +    l1 = left_next_index[P_id[p]] +    l2 = left_next_index[l1] +    r1 = right_next_index[P_id[p]] +    r2 = right_next_index[r1] +    res += p * ((l1 - l2) * (r1 - P_id[p]) + (P_id[p] - l1) * (r2 - r1)) +    left_next_index[r1] = l1 +    right_next_index[l1] = r1