class BIT:

  def __init__(self, n):

    self.N = n

    self.tree = [0]*(n+1)

  

  def BIT_add(self, i):

    while i <= self.N:

      self.tree[i] += 1

      i += i&(-i)

  

  def BIT_sum(self, i):

    s = 0

    while i:

      s += self.tree[i]

      i -= i&(-i)

    return s

  

  def BIT_search(self, x):

    i = 0

    s = 0

    step = 1<<(self.N.bit_length()-1)

    

    while step:

      if i+step <= self.N and s+self.tree[i+step] < x:

        i += step

        s += self.tree[i]

      step >>= 1

    return i+1



N = int(eval(input()))

bit = BIT(N)

p = [None]+[int(c) for c in input().split()]

p_to_i = [None]*(N+1)

for i, x in enumerate(p[1:], 1):

  p_to_i[x] = i

  

ans = 0

for x in range(N,0,-1):

  c = p_to_i[x]

  L = bit.BIT_sum(c)

  bit.BIT_add(c)

  R = N-x-L

  a = bit.BIT_search(L-1) if L>=2 else 0

  b = bit.BIT_search(L) if L >= 1 else 0

  d = bit.BIT_search(L+2) if R >= 1 else N+1

  e = bit.BIT_search(L+3) if R >= 1 else N+1

  

  coef = 0

  if b != 0:

    coef += (b-a) * (d-c)

  if d != 0:

    coef += (e-d) * (c-b)

  

  ans += x*coef

print(ans)
class BIT:

  

  def __init__(self, N):

    self.n = N

    self.tree = [0]*(self.n+1)

    

  def bsum(self, i):

    s = 0

    while i:

      s += self.tree[i]

      i -= i&(-i)

    return s

  

  def badd(self, i, x):

    while i<=self.n:

      self.tree[i] += x

      i += i&(-i)

  

  def bsearch(self, x):

    i = 0

    s = 0

    step = 1<<(self.n.bit_length()-1)

    while step:

      if i+step<=self.n and s+self.tree[i+step]<x:

        i += step

        s += self.tree[i]

      step >>= 1

    return i+1



      

N = int(eval(input()))

P = [0]+[int(c) for c in input().split()]



ntoi = [0]*(N+1)

for i in range(N+1):

  ntoi[P[i]] = i



bit = BIT(N)



ans = 0

for m in range(N, 0, -1):

  I = ntoi[m]

  L = bit.bsum(I)

  bit.badd(I,1)

  R = N-L-m

  a = bit.bsearch(L-1) if L>1 else 0

  b = bit.bsearch(L) if L>0 else 0

  c = bit.bsearch(L+2) if R>0 else N+1

  d = bit.bsearch(L+3) if R>1 else N+1

  coef = 0

  if b!=0:

    coef += (b-a)*(c-I)

  if c!=0:

    coef += (I-b)*(d-c)

  ans += m*coef



print(ans)
class BIT:
    def __init__(self, n):
        self.N = n
        self.tree = [0] * (n + 1)

    def BIT_add(self, i):
        while i <= self.N:
            self.tree[i] += 1
            i += i & (-i)

    def BIT_sum(self, i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def BIT_search(self, x):
        i = 0
        s = 0
        step = 1 << (self.N.bit_length() - 1)
        while step:
            if i + step <= self.N and s + self.tree[i + step] < x:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1


N = int(eval(input()))
bit = BIT(N)
p = [None] + [int(c) for c in input().split()]
p_to_i = [None] * (N + 1)
for i, x in enumerate(p[1:], 1):
    p_to_i[x] = i
ans = 0
for x in range(N, 0, -1):
    c = p_to_i[x]
    L = bit.BIT_sum(c)
    bit.BIT_add(c)
    R = N - x - L
    a = bit.BIT_search(L - 1) if L >= 2 else 0
    b = bit.BIT_search(L) if L >= 1 else 0
    d = bit.BIT_search(L + 2) if R >= 1 else N + 1
    e = bit.BIT_search(L + 3) if R >= 1 else N + 1
    coef = 0
    if b != 0:
        coef += (b - a) * (d - c)
    if d != 0:
        coef += (e - d) * (c - b)
    ans += x * coef
print(ans)

class BIT:
    def __init__(self, N):
        self.n = N
        self.tree = [0] * (self.n + 1)

    def bsum(self, i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def badd(self, i, x):
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)

    def bsearch(self, x):
        i = 0
        s = 0
        step = 1 << (self.n.bit_length() - 1)
        while step:
            if i + step <= self.n and s + self.tree[i + step] < x:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1


N = int(eval(input()))
P = [0] + [int(c) for c in input().split()]
ntoi = [0] * (N + 1)
for i in range(N + 1):
    ntoi[P[i]] = i
bit = BIT(N)
ans = 0
for m in range(N, 0, -1):
    I = ntoi[m]
    L = bit.bsum(I)
    bit.badd(I, 1)
    R = N - L - m
    a = bit.bsearch(L - 1) if L > 1 else 0
    b = bit.bsearch(L) if L > 0 else 0
    c = bit.bsearch(L + 2) if R > 0 else N + 1
    d = bit.bsearch(L + 3) if R > 1 else N + 1
    coef = 0
    if b != 0:
        coef += (b - a) * (c - I)
    if c != 0:
        coef += (I - b) * (d - c)
    ans += m * coef
print(ans)

-    def __init__(self, n): -        self.N = n -        self.tree = [0] * (n + 1) +    def __init__(self, N): +        self.n = N +        self.tree = [0] * (self.n + 1) -    def BIT_add(self, i): -        while i <= self.N: -            self.tree[i] += 1 -            i += i & (-i) - -    def BIT_sum(self, i): +    def bsum(self, i): -    def BIT_search(self, x): +    def badd(self, i, x): +        while i <= self.n: +            self.tree[i] += x +            i += i & (-i) + +    def bsearch(self, x): -        step = 1 << (self.N.bit_length() - 1) +        step = 1 << (self.n.bit_length() - 1) -            if i + step <= self.N and s + self.tree[i + step] < x: +            if i + step <= self.n and s + self.tree[i + step] < x: +P = [0] + [int(c) for c in input().split()] +ntoi = [0] * (N + 1) +for i in range(N + 1): +    ntoi[P[i]] = i -p = [None] + [int(c) for c in input().split()] -p_to_i = [None] * (N + 1) -for i, x in enumerate(p[1:], 1): -    p_to_i[x] = i -for x in range(N, 0, -1): -    c = p_to_i[x] -    L = bit.BIT_sum(c) -    bit.BIT_add(c) -    R = N - x - L -    a = bit.BIT_search(L - 1) if L >= 2 else 0 -    b = bit.BIT_search(L) if L >= 1 else 0 -    d = bit.BIT_search(L + 2) if R >= 1 else N + 1 -    e = bit.BIT_search(L + 3) if R >= 1 else N + 1 +for m in range(N, 0, -1): +    I = ntoi[m] +    L = bit.bsum(I) +    bit.badd(I, 1) +    R = N - L - m +    a = bit.bsearch(L - 1) if L > 1 else 0 +    b = bit.bsearch(L) if L > 0 else 0 +    c = bit.bsearch(L + 2) if R > 0 else N + 1 +    d = bit.bsearch(L + 3) if R > 1 else N + 1 -        coef += (b - a) * (d - c) -    if d != 0: -        coef += (e - d) * (c - b) -    ans += x * coef +        coef += (b - a) * (c - I) +    if c != 0: +        coef += (I - b) * (d - c) +    ans += m * coef