### BUGGY CODE ###

class SegmentTree:
    """
    値をlistで持つSegmentTree
    update(i, x): i(0-indexed)をxで更新
    get(a,b): [a, b)を取得
    """

    def __init__(self, n, ini, merge):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [ini[:] for _ in range(n2 << 1)]
        self.ini = ini
        self.merge = merge

    def update(self, i, x):
        i += self.n2
        self.merge(self.tree[i], x)
        while i > 1:
            self.merge(x, self.tree[i ^ 1])
            i >>= 1
            self.tree[i][0] = x[0]
            self.tree[i][1] = x[1]

    def get(self, a, b):
        result = self.ini[:]
        self._get(a, b, 1, 0, self.n2, result)
        return result

    def _get(self, a, b, k, l, r, result):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での値
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            self.merge(result, self.tree[k])
            return
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        self._get(a, b, k << 1, l, m, result)
        self._get(a, b, (k << 1) + 1, m, r, result)


def solve(n, ppp):
    def merge_min(x, y):
        """ update x """
        if x[0] <= y[0]:
            if x[1] <= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] <= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    def merge_max(x, y):
        """ update x """
        if x[0] >= y[0]:
            if x[1] >= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] >= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    stl = SegmentTree(n, [-1, -1], merge_max)
    left = []
    for i, p in enumerate(ppp):
        left.append(stl.get(p, n))
        stl.update(p - 1, [i, -1])

    str = SegmentTree(n, [n, n], merge_min)
    right = []
    for i, p in enumerate(ppp[::-1]):
        i = n - i - 1
        right.append(str.get(p, n))
        str.update(p - 1, [i, n])
    right.reverse()
    # print(left)
    # print(right)

    ans = 0
    for i, (l1, l2), (r1, r2) in zip(range(n), left, right):
        ans += ppp[i] * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))


### FIXED CODE ###

class SegmentTree:
    def __init__(self, n, init_value):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [[init_value, init_value] for _ in range(n2 << 1)]
        self.ini = init_value

    def update(self, i, x):
        # 注: 同じiへのクエリは複数来ないことを利用して単純化
        i += self.n2
        self.tree[i][0] = x
        while i > 1:
            i >>= 1
            sti = self.tree[i]
            if sti[0] > x:
                sti[1] = sti[0]
                sti[0] = x
            elif sti[1] > x:
                sti[1] = x

    def get(self, a, b):
        result = [self.ini, self.ini]
        q = [(1, 0, self.n2)]

        while q:
            k, l, r = q.pop()

            if a <= l and r <= b:
                stk = self.tree[k]
                if result[0] > stk[0]:
                    result[1] = min(result[0], stk[1])
                    result[0] = stk[0]
                elif result[1] > stk[0]:
                    result[1] = stk[0]
                continue

            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))

        return result


def solve(n, ppp):
    str = SegmentTree(n, n)
    right = []
    for i in range(n - 1, -1, -1):
        p = ppp[i]
        right.append(str.get(p, n))
        str.update(p - 1, i)
    right.reverse()

    ans = 0
    stl = SegmentTree(n, 1)
    for i in range(n):
        p = ppp[i]
        l1, l2 = stl.get(p, n)
        l1, l2 = -l1, -l2
        r1, r2 = right[i]
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        stl.update(p - 1, -i)

    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))