

from bisect import bisect_left, bisect_right

class OrderedSet:

    def __init__(self, a):

        self.c = {}

        self.a_sort = sorted(list(set(a)))

        for i, a in enumerate(self.a_sort):

            self.c[a] = i + 1

        self.r = {v: k for k, v in list(self.c.items())}

        self.size = len(self.c)

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

        self.num = [0] * self.size

        self.all_count = 0  # 全要素数



    # BITのsum関数

    def _sum(self, index):

        s = 0

        while index:

            s += self.tree[index]

            index -= index & (-index)

        return s



    # xをk個挿入する

    def insert(self, x, k=1):

        index = self.c[x]

        self.num[index - 1] += k

        while index <= self.size:

            self.tree[index] += k

            index += index & (-index)

        self.all_count += k



    # xをk個削除する

    def erase(self, x, k=1):

        self.insert(x, k=-k)



    # 格納しているxの数を返す

    def count(self, x):

        return self.num[self.c[x] - 1]



    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）

    def get_kth_bottom(self, k):

        if k <= 0:

            return None

        elif self.all_count < k:

            return None

        else:

            i = 0

            s = 0

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

            while step:

                if i + step <= self.size and s + self.tree[i + step] < k:

                    i += step

                    s += self.tree[i]

                step >>= 1

            return self.r[i + 1]



    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）

    def get_kth_top(self, k):

        return self.get_kth_bottom(self.all_count - k + 1)



    # x以上の最小要素を返す

    def lower_bound(self, x):

        p = bisect_left(self.a_sort, x)

        if p == 0:

            k = 1

        else:

            k = self._sum(p) + 1

        return self.get_kth_bottom(k)



    # x以下の最大要素を返す

    def upper_bound(self, x):

        p = bisect_right(self.a_sort, x)

        if p == 0:

            return None

        else:

            k = self._sum(p)

            return self.get_kth_bottom(k)





def resolve():

    N = int(eval(input()))

    A = list(map(int, input().split()))



    P = [0] * (N + 1)

    for i in range(N):

        P[A[i]] = i + 1



    OS = OrderedSet(P)

    ans = 0

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

        p = P[i]

        c = OS.lower_bound(p)

        d = None if c is None else OS.lower_bound(c + 1)

        b = OS.upper_bound(p)

        a = None if b is None else OS.upper_bound(b - 1)



        a = a if a is not None else 0

        d = d if d is not None else N + 1



        if b is None:

            if c is not None:

                ans += i * p * (d - c)

        elif c is None:

            ans += i * (b - a) * (N - p + 1)

        else:

            ans += i * ((b - a) * (c - p) + (p - b) * (d - c))



        OS.insert(p)



    print(ans)





if __name__ == "__main__":

    resolve()



def resolve():

    N = int(eval(input()))

    A = list(map(int, input().split()))



    P = [0] * (N + 1)

    for i, a in enumerate(A):

        P[a] = i



    l_idx = list(range(-1, N - 1)) + [-1, -1]

    r_idx = list(range(1, N + 1)) + [N, N]  # 番兵



    ans = 0

    for p in range(1, N + 1):

        x = P[p]



        l1 = l_idx[x]

        l2 = l_idx[l1]

        r1 = r_idx[x]

        r2 = r_idx[r1]



        cmb = (x - l1) * (r2 - r1) + (l1 - l2) * (r1 - x)

        ans += p * cmb



        l_idx[r1] = l1

        r_idx[l1] = r1



    print(ans)





if __name__ == "__main__":

    resolve()
from bisect import bisect_left, bisect_right


class OrderedSet:
    def __init__(self, a):
        self.c = {}
        self.a_sort = sorted(list(set(a)))
        for i, a in enumerate(self.a_sort):
            self.c[a] = i + 1
        self.r = {v: k for k, v in list(self.c.items())}
        self.size = len(self.c)
        self.tree = [0] * (self.size + 1)
        self.num = [0] * self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self, index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self, x, k=1):
        index = self.c[x]
        self.num[index - 1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k

    # xをk個削除する
    def erase(self, x, k=1):
        self.insert(x, k=-k)

    # 格納しているxの数を返す
    def count(self, x):
        return self.num[self.c[x] - 1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self, k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i + 1]

    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self, k):
        return self.get_kth_bottom(self.all_count - k + 1)

    # x以上の最小要素を返す
    def lower_bound(self, x):
        p = bisect_left(self.a_sort, x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)

    # x以下の最大要素を返す
    def upper_bound(self, x):
        p = bisect_right(self.a_sort, x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)


def resolve():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    P = [0] * (N + 1)
    for i in range(N):
        P[A[i]] = i + 1
    OS = OrderedSet(P)
    ans = 0
    for i in range(N, 0, -1):
        p = P[i]
        c = OS.lower_bound(p)
        d = None if c is None else OS.lower_bound(c + 1)
        b = OS.upper_bound(p)
        a = None if b is None else OS.upper_bound(b - 1)
        a = a if a is not None else 0
        d = d if d is not None else N + 1
        if b is None:
            if c is not None:
                ans += i * p * (d - c)
        elif c is None:
            ans += i * (b - a) * (N - p + 1)
        else:
            ans += i * ((b - a) * (c - p) + (p - b) * (d - c))
        OS.insert(p)
    print(ans)


if __name__ == "__main__":
    resolve()

def resolve():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    P = [0] * (N + 1)
    for i, a in enumerate(A):
        P[a] = i
    l_idx = list(range(-1, N - 1)) + [-1, -1]
    r_idx = list(range(1, N + 1)) + [N, N]  # 番兵
    ans = 0
    for p in range(1, N + 1):
        x = P[p]
        l1 = l_idx[x]
        l2 = l_idx[l1]
        r1 = r_idx[x]
        r2 = r_idx[r1]
        cmb = (x - l1) * (r2 - r1) + (l1 - l2) * (r1 - x)
        ans += p * cmb
        l_idx[r1] = l1
        r_idx[l1] = r1
    print(ans)


if __name__ == "__main__":
    resolve()

-from bisect import bisect_left, bisect_right - - -class OrderedSet: -    def __init__(self, a): -        self.c = {} -        self.a_sort = sorted(list(set(a))) -        for i, a in enumerate(self.a_sort): -            self.c[a] = i + 1 -        self.r = {v: k for k, v in list(self.c.items())} -        self.size = len(self.c) -        self.tree = [0] * (self.size + 1) -        self.num = [0] * self.size -        self.all_count = 0  # 全要素数 - -    # BITのsum関数 -    def _sum(self, index): -        s = 0 -        while index: -            s += self.tree[index] -            index -= index & (-index) -        return s - -    # xをk個挿入する -    def insert(self, x, k=1): -        index = self.c[x] -        self.num[index - 1] += k -        while index <= self.size: -            self.tree[index] += k -            index += index & (-index) -        self.all_count += k - -    # xをk個削除する -    def erase(self, x, k=1): -        self.insert(x, k=-k) - -    # 格納しているxの数を返す -    def count(self, x): -        return self.num[self.c[x] - 1] - -    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す） -    def get_kth_bottom(self, k): -        if k <= 0: -            return None -        elif self.all_count < k: -            return None -        else: -            i = 0 -            s = 0 -            step = 1 << (self.size.bit_length() - 1) -            while step: -                if i + step <= self.size and s + self.tree[i + step] < k: -                    i += step -                    s += self.tree[i] -                step >>= 1 -            return self.r[i + 1] - -    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す） -    def get_kth_top(self, k): -        return self.get_kth_bottom(self.all_count - k + 1) - -    # x以上の最小要素を返す -    def lower_bound(self, x): -        p = bisect_left(self.a_sort, x) -        if p == 0: -            k = 1 -        else: -            k = self._sum(p) + 1 -        return self.get_kth_bottom(k) - -    # x以下の最大要素を返す -    def upper_bound(self, x): -        p = bisect_right(self.a_sort, x) -        if p == 0: -            return None -        else: -            k = self._sum(p) -            return self.get_kth_bottom(k) - - -    for i in range(N): -        P[A[i]] = i + 1 -    OS = OrderedSet(P) +    for i, a in enumerate(A): +        P[a] = i +    l_idx = list(range(-1, N - 1)) + [-1, -1] +    r_idx = list(range(1, N + 1)) + [N, N]  # 番兵 -    for i in range(N, 0, -1): -        p = P[i] -        c = OS.lower_bound(p) -        d = None if c is None else OS.lower_bound(c + 1) -        b = OS.upper_bound(p) -        a = None if b is None else OS.upper_bound(b - 1) -        a = a if a is not None else 0 -        d = d if d is not None else N + 1 -        if b is None: -            if c is not None: -                ans += i * p * (d - c) -        elif c is None: -            ans += i * (b - a) * (N - p + 1) -        else: -            ans += i * ((b - a) * (c - p) + (p - b) * (d - c)) -        OS.insert(p) +    for p in range(1, N + 1): +        x = P[p] +        l1 = l_idx[x] +        l2 = l_idx[l1] +        r1 = r_idx[x] +        r2 = r_idx[r1] +        cmb = (x - l1) * (r2 - r1) + (l1 - l2) * (r1 - x) +        ans += p * cmb +        l_idx[r1] = l1 +        r_idx[l1] = r1