# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
import random
import bisect
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class BIT:
    '''
    BinaryIndexedTreeのクラス。0-indexed に統一してあるので0からn-1までの配列と思って使える。

    Parameters
    ----------
        n (Union(int, list)): int なら使う BIT のサイズ。list ならそのlistで BIT を初期化する
    '''
    def __init__(self, x, d=0):
        if isinstance(x, int):
            self.size = x
            self.tree = [d for _ in range(self.size + 1)]
        elif isinstance(x, list):
            self.size = len(x)
            self.tree = [d for _ in range(self.size + 1)]
            self.build(x)
        else:
            raise TypeError

    def build(self, arr):
        """
        初期化されたあとのBITをリストの値に設定する

        Parameters
        ----------
            arr (list): 元のlsit

        Raises
        ------
            TypeError: 入力はlistでないといけないことに注意してください。
        """
        if not isinstance(arr, list):
            raise TypeError
        for num, x in enumerate(arr):
            self.add(num, x)

    def sum(self, i):
        '''[0,i) の和'''
        if i < 0:
            return 0
        s = self.tree[0]
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
        return s

    def add(self, i, a):
        i += 1
        '''i番目の要素にaを足す'''
        if(i == 0):
            return
        while (i <= self.size):
            self.tree[i] += a
            i += (i & -i)

    def lower_bound(self, w):
        '''[0,i]の和 >= w をみたす最小の index
        Examples
        ----------
        >>> bit = BIT([1,0,0,1,0,1,0])
        >>> bit.lower_bound(1)
        0
        >>> bit.lower_bound(2)
        3
        >>> bit.lower_bound(3)
        5
        '''
        if w <= 0:
            return -1
        x = 0
        k = 1 << (self.size.bit_length() - 1)
        while k:
            if x + k <= self.size and self.tree[x + k] < w:
                w -= self.tree[x + k]
                x += k
            k >>= 1
        return x

    def getKthNum(self, w):
        '''k番目(k = 0, 1, ...)に小さい数を返す'''
        w += 1
        return self.lower_bound(w)

    def upper_bound(self, w):
        w += 0.00000000001
        return self.lower_bound(w)

    def query(self, l, r):
        '''[l, r)の和を求める
        >>> bit = BIT([1,2,3,4,5])
        >>> bit.query(1,4)
        9
        >>> bit.query(0,2)
        3
        '''
        return self.sum(r) - self.sum(l)

    # 出力関係（デバッグのみに用いる）
    def __getitem__(self, item):
        if not isinstance(item, int):
            _tmp = item.indices(self.size + 1)
            return [self.sum(i + 1) - self.sum(i) for i in range(_tmp[0], _tmp[1], _tmp[2])]
        else:
            return self.sum(item + 1) - self.sum(item)
    def __str__(self):
        return str(self[0:self.size])
# END CUT HERE

class sqrtDecomposition():
    def __init__(self, N):
        self.BASE = 100
        self.size = 0
        self.a = [[] for i in range(ceil(N / self.BASE))]
        self.b = BIT(ceil(N / self.BASE))

    def insert(self, i):
        self.size += 1
        idx = bisect.bisect_left(self.a[i // self.BASE], i)
        self.a[i // self.BASE].insert(idx, i)
        self.b.add(i // self.BASE, 1)
        return (i // self.BASE, idx)

    def _next(self, key, idx1, idx2):
        if key >= self.size:
            return (None, None)
        if len(self.a[idx1]) - 1 == idx2:
            idx = self.b.lower_bound(key + 1)
            return (idx, 0)
        else:
            return (idx1, idx2 + 1)

    def _prev(self, key, idx1, idx2):
        if key <= 0:
            return (None, None)
        if idx2 == 0:
            idx = self.b.lower_bound(key)
            return (idx, len(self.a[idx]) - 1)
        else:
            return (idx1, idx2 - 1)

    def get(self, left, right):
        left += 1
        right += 1
        idx1, idx2 = None, None
        for key in range(left, right):
            # debug(key, self.size)
            if key <= 0 or key > self.size:
                yield (None, None)
                continue
            if not idx1:
                idx1 = self.b.lower_bound(key)
                idx2 = key - self.b.sum(idx1) - 1
            else:
                idx1, idx2 = self._next(key - 1, idx1, idx2)
            yield (idx1, idx2)

def main():
    # N = 10**6
    # P = [i for i in range(N)]
    # random.shuffle(P)
    N = ii()
    P = lmi()
    t = sqrtDecomposition(N)
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    # debug(L)
    ans = 0
    for num, i in enumerate(L):
        c = t.insert(i)
        idx = t.b.sum(c[0]) + c[1]
        l = [-1] * 4
        l[1] = t._prev(idx, *c)
        l[0] = t._prev(idx - 1, *l[1])
        l[2] = t._next(idx + 1, *c)
        l[3] = t._next(idx + 2, *l[2])
        # debug(idx, l[0], l[1], l[2], l[3])
        for j in range(4):
            if l[j][0] is not None:
                l[j] = t.a[l[j][0]][l[j][1]]
            else:
                if j >= 2:
                    l[j] = N
                else:
                    l[j] = -1

        # debug(l[0], l[1], l[2], l[3])
        ans += (abs(i - l[1]) * abs(l[3] - l[2]) + abs(l[1] - l[0]) * abs(l[2] - i)) * (N - num)
    print(ans)
    return


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
        import cProfile
        cProfile.run('main()', sort=1)
    else:
        main()


Measured memory_bytes: 107752