Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))

class segMax:
  inf = 0
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最大値
    return max(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

class segMin:
  inf = 10 ** 10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = segMax(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  #print(ans)
  t = D[i]
  ma = TMa.getV(0, t)
  if ma == 0:
    ma = N + 1
    ma2 = N + 1
  else:
    ma2 = TMa.getV(0, ma - 1)

  mi = TMi.getV(t, N + 1)
  if mi == 10 ** 10:
    mi = 0
    mi2 = 0
  else:
    mi2 = TMi.getV(mi + 1, N + 1)
  
  if ma2 == 0: ma2 = N + 1
  if mi2 == 10 ** 10: mi2 = 0
  TMa.update(t, t)
  TMi.update(t, t)
  #print(ma2, ma, t, mi, mi2)
  if ma == N + 1 and mi == 0:
    continue
  if ma == N + 1:
    if mi2 != 0:
      ans += t * (mi2 - mi) * i
    else:
      ans += t * (N - mi + 1) * i
    continue
  if mi == 0:
    if ma2 != N + 1:
      ans += (N - t + 1) * (ma - ma2) * i
    else:
      ans += (N - t + 1) * (ma) * i
    continue
  if mi2 != 0:
    ans += (mi2 -  mi) * (t - ma) * i
    if ma2 != N + 1:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
  else:
    ans += (N - mi + 1) * (t - ma) * i
    if ma2 != N + 1:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
      

print(ans)

Fixed submission:
N = int(input())
P = list(map(int, input().split()))

class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + 1
    s.T[k - 1] = max(s.T[k - 1], v)
    k += k & -k
    while k <= s.N:
      s.T[k - 1] = max(s.T[k - 1], v)
      k += k & -k
  def getV(s, x):
    if x <= 0:
      return 0
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans = max(ans, s.T[x - 1])
      x -= x & -x
    return ans

class segMin:
  inf = N + 1
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    if l > r:
      return s.inf
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = BIT(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  #print(ans)
  t = D[i]
  ma = TMa.getV(t)
  ma2 = TMa.getV(ma)

  mi = TMi.getV(t, N + 1)
  mi2 = TMi.getV(mi + 1, N + 1)
  #print(ma2, ma, t, mi, mi2, ans)
  TMa.update(t, t)
  TMi.update(t, t)
  ans += (mi - t) * (ma - ma2) * i
  ans += (mi2 - mi) * (t - ma) * i

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))

class segMax:
  inf = 0
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最大値
    return max(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

class segMin:
  inf = 10 ** 10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = segMax(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  #print(ans)
  t = D[i]
  ma = TMa.getV(0, t)
  if ma == 0:
    ma = N + 1
    ma2 = N + 1
  else:
    ma2 = TMa.getV(0, ma - 1)

  mi = TMi.getV(t, N + 1)
  if mi == 10 ** 10:
    mi = 0
    mi2 = 0
  else:
    mi2 = TMi.getV(mi + 1, N + 1)
  
  if ma2 == 0: ma2 = N + 1
  if mi2 == 10 ** 10: mi2 = 0
  TMa.update(t, t)
  TMi.update(t, t)
  #print(ma2, ma, t, mi, mi2)
  if ma == N + 1 and mi == 0:
    continue
  if ma == N + 1:
    if mi2 != 0:
      ans += t * (mi2 - mi) * i
    else:
      ans += t * (N - mi + 1) * i
    continue
  if mi == 0:
    if ma2 != N + 1:
      ans += (N - t + 1) * (ma - ma2) * i
    else:
      ans += (N - t + 1) * (ma) * i
    continue
  if mi2 != 0:
    ans += (mi2 -  mi) * (t - ma) * i
    if ma2 != N + 1:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
  else:
    ans += (N - mi + 1) * (t - ma) * i
    if ma2 != N + 1:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
      

print(ans)

Fixed submission:
N = int(input())
P = list(map(int, input().split()))

class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + 1
    s.T[k - 1] = max(s.T[k - 1], v)
    k += k & -k
    while k <= s.N:
      s.T[k - 1] = max(s.T[k - 1], v)
      k += k & -k
  def getV(s, x):
    if x <= 0:
      return 0
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans = max(ans, s.T[x - 1])
      x -= x & -x
    return ans

class segMin:
  inf = N + 1
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    if l > r:
      return s.inf
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = BIT(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  #print(ans)
  t = D[i]
  ma = TMa.getV(t)
  ma2 = TMa.getV(ma)

  mi = TMi.getV(t, N + 1)
  mi2 = TMi.getV(mi + 1, N + 1)
  #print(ma2, ma, t, mi, mi2, ans)
  TMa.update(t, t)
  TMi.update(t, t)
  ans += (mi - t) * (ma - ma2) * i
  ans += (mi2 - mi) * (t - ma) * i

print(ans)