### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(N, P):
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)
    done = [0, N+1]
    ans = 0
    for p, i in P2:
        i += 1
        j = bisect.bisect(done, i)
        bisect.insort(done, i)
        c = 0
        if j >= 2:
            l = done[j-1] - done[j-2]
            r = done[j+1] - done[j]
            c += l * r
        if j <= len(done) - 3:
            l = done[j] - done[j-1]
            r = done[j+2] - done[j+1]
            c += l*r
        ans += c*p
        
    return ans


@mt
def slv2(N, P):
    ans = 0
    c = Counter()
    for i, j in combinations(range(N), 2):
        a = sorted(P[i:j+1], reverse=True)[1]
        ans += a
        c[a] += 1
    print(c)
    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))
    # print(slv2(N, P))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))



if __name__ == '__main__':
    main()