class WeightBalancedTree:

    def __init__(self, q):

        self.left = [0] * (q + 1)

        self.right = [0] * (q + 1)

        self.weight = [1] * (q + 1)

        self.key = [None] * (q + 1)

        self.last_index = 0

        self.root = 0



# key 未満の最大値

    def search_lower(self, key):

        if key == None:

            return None

        ret = None

        idx = self.root

        while idx != 0:

            if self.key[idx] < key:

                ret = self.key[idx]

                idx = self.right[idx]

            else:

                idx = self.left[idx]

        return ret



# key 超過の最小値

    def search_higher(self, key):

        if key == None:

            return None

        ret = None

        idx = self.root

        while idx != 0:

            if self.key[idx] > key:

                ret = self.key[idx]

                idx = self.left[idx]

            else:

                idx = self.right[idx]

        return ret



# 要素の挿入

# 重複を考慮しない

# ToDo: 考慮するものも実装する

    def insert(self, key):

        self.last_index += 1

        self.key[self.last_index] = key

        self.weight[self.last_index] = 2

        self.root = self.__recursive_insert(self.root)



# insert の再帰実装に用いる

    def __recursive_insert(self, idx):

        if idx == 0:

            return self.last_index

        elif self.key[self.last_index] < self.key[idx]:

            self.left[idx] = self.__recursive_insert(self.left[idx])

            self.__fix(idx)

            return self.__fix_left_bias(idx)

        else:

            self.right[idx] = self.__recursive_insert(self.right[idx])

            self.__fix(idx)

            return self.__fix_right_bias(idx)



# ノードの weight を補正する

    def __fix(self, idx):

        self.weight[idx] = self.weight[self.left[idx]] + \

            self.weight[self.right[idx]]



# 左回転

    def __rotate_left(self, idx):

        right = self.right[idx]

        self.right[idx] = self.left[right]

        self.__fix(idx)

        self.left[right] = idx

        self.__fix(right)

        return right



# 右回転

    def __rotate_right(self, idx):

        left = self.left[idx]

        self.left[idx] = self.right[left]

        self.__fix(idx)

        self.right[left] = idx

        self.__fix(left)

        return left



# 左偏状態の補正

    def __fix_left_bias(self, idx):

        if self.weight[self.right[idx]] << 2 < self.weight[idx]:

            left = self.left[idx]

            if self.weight[self.left[left]] << 2 < self.weight[left]:

                self.left[idx] = self.__rotate_left(left)

            idx = self.__rotate_right(idx)

        return idx



# 右偏状態の補正

    def __fix_right_bias(self, idx):

        if self.weight[self.left[idx]] << 2 < self.weight[idx]:

            right = self.right[idx]

            if self.weight[self.right[right]] << 2 < self.weight[right]:

                self.right[idx] = self.__rotate_right(right)

            idx = self.__rotate_left(idx)

        return idx



# 要素数

    def size(self):

        return self.weight[self.root] - 1



# デバッグ用

    def dump(self):

        self.__dump(self.root, 0)



    def __dump(self, idx, dep):

        if idx != 0:

            self.__dump(self.right[idx], dep + 1)

            for _ in range(0, dep):

                print("   ", end="")

            print('i:{0},k:{1},l:{2},r:{3},w:{4}'.format(

                idx, self.key[idx], self.left[idx], self.right[idx], self.weight[idx]))

            self.__dump(self.left[idx], dep + 1)





def main():

    n = int(input())

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

    idx = [0] * n

    for i in range(0, n):

        idx[i] = i

    idx.sort(key=lambda i: - p[i])

    t = WeightBalancedTree(n+2)

    t.insert(-1)

    t.insert(n)

    ans = 0

    for i in idx:

        nex = t.search_higher(i)

        nexnex = t.search_higher(nex)

        pre = t.search_lower(i)

        prepre = t.search_lower(pre)

        if prepre != None:

            ans += p[i] * (pre - prepre) * (nex - i)

        if nexnex != None:

            ans += p[i] * (i - pre) * (nexnex - nex)

        t.insert(i)

    print(ans)





main()

import time

import random





class TreapNode:

    def __init__(self, key, pri):

        self.left = None

        self.right = None

        self.key = key

        self.pri = pri





class Treap:

    def __init__(self):

        self.nil = TreapNode(None, 0)

        self.root = self.nil



    def search_lower(self, key):

        if key == None:

            return None

        ptr = self.root

        ret = None

        nil = self.nil

        while ptr is not nil:

            pk = ptr.key

            if pk < key:

                ret = pk

                ptr = ptr.right

            else:

                ptr = ptr.left

        return ret



    def search_higher(self, key):

        if key == None:

            return None

        ptr = self.root

        ret = None

        nil = self.nil

        while ptr is not nil:

            pk = ptr.key

            if pk > key:

                ret = pk

                ptr = ptr.left

            else:

                ptr = ptr.right

        return ret



    def insert(self, key):

        pri = random.randrange(1, 2**32)

        ptr = self.root

        elem = TreapNode(key, pri)

        if ptr.pri < pri:

            self.root = elem

        else:

            while True:

                if key < ptr.key:

                    left = ptr.left

                    if left.pri < pri:

                        ptr.left = elem

                        ptr = left

                        break

                    ptr = left

                else:

                    right = ptr.right

                    if right.pri < pri:

                        ptr.right = elem

                        ptr = right

                        break

                    ptr = right

        left = elem

        right = elem

        nil = self.nil

        while ptr is not nil:

            if key < ptr.key:

                right.left = ptr

                right = ptr

                ptr = ptr.left

            else:

                left.right = ptr

                left = ptr

                ptr = ptr.right

        left.right = nil

        right.left = nil

        elem.left, elem.right = elem.right, elem.left



# デバッグ用

    def dump(self):

        self.__dump(self.root, 0)



    def __dump(self, idx, dep):

        if idx is not self.nil:

            self.__dump(idx.right, dep + 1)

            for _ in range(0, dep):

                print("   ", end="")

            print([idx.key, idx.pri])

            self.__dump(idx.left, dep + 1)



def main():

    n = int(input())

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

    idx = [0] * n

    for i in range(0, n):

        idx[i] = i

    idx.sort(key=lambda i: - p[i])

    t = Treap()

    t.insert(-1)

    t.insert(n)

    ans = 0

    for i in idx:

        nex = t.search_higher(i)

        nexnex = t.search_higher(nex)

        pre = t.search_lower(i)

        prepre = t.search_lower(pre)

        if prepre != None:

            ans += p[i] * (pre - prepre) * (nex - i)

        if nexnex != None:

            ans += p[i] * (i - pre) * (nexnex - nex)

        t.insert(i)

    print(ans)





main()

class WeightBalancedTree:
    def __init__(self, q):
        self.left = [0] * (q + 1)
        self.right = [0] * (q + 1)
        self.weight = [1] * (q + 1)
        self.key = [None] * (q + 1)
        self.last_index = 0
        self.root = 0

    # key 未満の最大値
    def search_lower(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] < key:
                ret = self.key[idx]
                idx = self.right[idx]
            else:
                idx = self.left[idx]
        return ret

    # key 超過の最小値
    def search_higher(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] > key:
                ret = self.key[idx]
                idx = self.left[idx]
            else:
                idx = self.right[idx]
        return ret

    # 要素の挿入
    # 重複を考慮しない
    # ToDo: 考慮するものも実装する
    def insert(self, key):
        self.last_index += 1
        self.key[self.last_index] = key
        self.weight[self.last_index] = 2
        self.root = self.__recursive_insert(self.root)

    # insert の再帰実装に用いる
    def __recursive_insert(self, idx):
        if idx == 0:
            return self.last_index
        elif self.key[self.last_index] < self.key[idx]:
            self.left[idx] = self.__recursive_insert(self.left[idx])
            self.__fix(idx)
            return self.__fix_left_bias(idx)
        else:
            self.right[idx] = self.__recursive_insert(self.right[idx])
            self.__fix(idx)
            return self.__fix_right_bias(idx)

    # ノードの weight を補正する
    def __fix(self, idx):
        self.weight[idx] = self.weight[self.left[idx]] + self.weight[self.right[idx]]

    # 左回転
    def __rotate_left(self, idx):
        right = self.right[idx]
        self.right[idx] = self.left[right]
        self.__fix(idx)
        self.left[right] = idx
        self.__fix(right)
        return right

    # 右回転
    def __rotate_right(self, idx):
        left = self.left[idx]
        self.left[idx] = self.right[left]
        self.__fix(idx)
        self.right[left] = idx
        self.__fix(left)
        return left

    # 左偏状態の補正
    def __fix_left_bias(self, idx):
        if self.weight[self.right[idx]] << 2 < self.weight[idx]:
            left = self.left[idx]
            if self.weight[self.left[left]] << 2 < self.weight[left]:
                self.left[idx] = self.__rotate_left(left)
            idx = self.__rotate_right(idx)
        return idx

    # 右偏状態の補正
    def __fix_right_bias(self, idx):
        if self.weight[self.left[idx]] << 2 < self.weight[idx]:
            right = self.right[idx]
            if self.weight[self.right[right]] << 2 < self.weight[right]:
                self.right[idx] = self.__rotate_right(right)
            idx = self.__rotate_left(idx)
        return idx

    # 要素数
    def size(self):
        return self.weight[self.root] - 1

    # デバッグ用
    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx != 0:
            self.__dump(self.right[idx], dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print(
                "i:{0},k:{1},l:{2},r:{3},w:{4}".format(
                    idx,
                    self.key[idx],
                    self.left[idx],
                    self.right[idx],
                    self.weight[idx],
                )
            )
            self.__dump(self.left[idx], dep + 1)


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: -p[i])
    t = WeightBalancedTree(n + 2)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

import time
import random


class TreapNode:
    def __init__(self, key, pri):
        self.left = None
        self.right = None
        self.key = key
        self.pri = pri


class Treap:
    def __init__(self):
        self.nil = TreapNode(None, 0)
        self.root = self.nil

    def search_lower(self, key):
        if key == None:
            return None
        ptr = self.root
        ret = None
        nil = self.nil
        while ptr is not nil:
            pk = ptr.key
            if pk < key:
                ret = pk
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_higher(self, key):
        if key == None:
            return None
        ptr = self.root
        ret = None
        nil = self.nil
        while ptr is not nil:
            pk = ptr.key
            if pk > key:
                ret = pk
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret

    def insert(self, key):
        pri = random.randrange(1, 2**32)
        ptr = self.root
        elem = TreapNode(key, pri)
        if ptr.pri < pri:
            self.root = elem
        else:
            while True:
                if key < ptr.key:
                    left = ptr.left
                    if left.pri < pri:
                        ptr.left = elem
                        ptr = left
                        break
                    ptr = left
                else:
                    right = ptr.right
                    if right.pri < pri:
                        ptr.right = elem
                        ptr = right
                        break
                    ptr = right
        left = elem
        right = elem
        nil = self.nil
        while ptr is not nil:
            if key < ptr.key:
                right.left = ptr
                right = ptr
                ptr = ptr.left
            else:
                left.right = ptr
                left = ptr
                ptr = ptr.right
        left.right = nil
        right.left = nil
        elem.left, elem.right = elem.right, elem.left

    # デバッグ用
    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx is not self.nil:
            self.__dump(idx.right, dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print([idx.key, idx.pri])
            self.__dump(idx.left, dep + 1)


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: -p[i])
    t = Treap()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

-class WeightBalancedTree: -    def __init__(self, q): -        self.left = [0] * (q + 1) -        self.right = [0] * (q + 1) -        self.weight = [1] * (q + 1) -        self.key = [None] * (q + 1) -        self.last_index = 0 -        self.root = 0 +import time +import random -    # key 未満の最大値 + +class TreapNode: +    def __init__(self, key, pri): +        self.left = None +        self.right = None +        self.key = key +        self.pri = pri + + +class Treap: +    def __init__(self): +        self.nil = TreapNode(None, 0) +        self.root = self.nil + +        ptr = self.root -        idx = self.root -        while idx != 0: -            if self.key[idx] < key: -                ret = self.key[idx] -                idx = self.right[idx] +        nil = self.nil +        while ptr is not nil: +            pk = ptr.key +            if pk < key: +                ret = pk +                ptr = ptr.right -                idx = self.left[idx] +                ptr = ptr.left -    # key 超過の最小値 +        ptr = self.root -        idx = self.root -        while idx != 0: -            if self.key[idx] > key: -                ret = self.key[idx] -                idx = self.left[idx] +        nil = self.nil +        while ptr is not nil: +            pk = ptr.key +            if pk > key: +                ret = pk +                ptr = ptr.left -                idx = self.right[idx] +                ptr = ptr.right -    # 要素の挿入 -    # 重複を考慮しない -    # ToDo: 考慮するものも実装する -        self.last_index += 1 -        self.key[self.last_index] = key -        self.weight[self.last_index] = 2 -        self.root = self.__recursive_insert(self.root) - -    # insert の再帰実装に用いる -    def __recursive_insert(self, idx): -        if idx == 0: -            return self.last_index -        elif self.key[self.last_index] < self.key[idx]: -            self.left[idx] = self.__recursive_insert(self.left[idx]) -            self.__fix(idx) -            return self.__fix_left_bias(idx) +        pri = random.randrange(1, 2**32) +        ptr = self.root +        elem = TreapNode(key, pri) +        if ptr.pri < pri: +            self.root = elem -            self.right[idx] = self.__recursive_insert(self.right[idx]) -            self.__fix(idx) -            return self.__fix_right_bias(idx) - -    # ノードの weight を補正する -    def __fix(self, idx): -        self.weight[idx] = self.weight[self.left[idx]] + self.weight[self.right[idx]] - -    # 左回転 -    def __rotate_left(self, idx): -        right = self.right[idx] -        self.right[idx] = self.left[right] -        self.__fix(idx) -        self.left[right] = idx -        self.__fix(right) -        return right - -    # 右回転 -    def __rotate_right(self, idx): -        left = self.left[idx] -        self.left[idx] = self.right[left] -        self.__fix(idx) -        self.right[left] = idx -        self.__fix(left) -        return left - -    # 左偏状態の補正 -    def __fix_left_bias(self, idx): -        if self.weight[self.right[idx]] << 2 < self.weight[idx]: -            left = self.left[idx] -            if self.weight[self.left[left]] << 2 < self.weight[left]: -                self.left[idx] = self.__rotate_left(left) -            idx = self.__rotate_right(idx) -        return idx - -    # 右偏状態の補正 -    def __fix_right_bias(self, idx): -        if self.weight[self.left[idx]] << 2 < self.weight[idx]: -            right = self.right[idx] -            if self.weight[self.right[right]] << 2 < self.weight[right]: -                self.right[idx] = self.__rotate_right(right) -            idx = self.__rotate_left(idx) -        return idx - -    # 要素数 -    def size(self): -        return self.weight[self.root] - 1 +            while True: +                if key < ptr.key: +                    left = ptr.left +                    if left.pri < pri: +                        ptr.left = elem +                        ptr = left +                        break +                    ptr = left +                else: +                    right = ptr.right +                    if right.pri < pri: +                        ptr.right = elem +                        ptr = right +                        break +                    ptr = right +        left = elem +        right = elem +        nil = self.nil +        while ptr is not nil: +            if key < ptr.key: +                right.left = ptr +                right = ptr +                ptr = ptr.left +            else: +                left.right = ptr +                left = ptr +                ptr = ptr.right +        left.right = nil +        right.left = nil +        elem.left, elem.right = elem.right, elem.left -        if idx != 0: -            self.__dump(self.right[idx], dep + 1) +        if idx is not self.nil: +            self.__dump(idx.right, dep + 1) -            print( -                "i:{0},k:{1},l:{2},r:{3},w:{4}".format( -                    idx, -                    self.key[idx], -                    self.left[idx], -                    self.right[idx], -                    self.weight[idx], -                ) -            ) -            self.__dump(self.left[idx], dep + 1) +            print([idx.key, idx.pri]) +            self.__dump(idx.left, dep + 1) -    t = WeightBalancedTree(n + 2) +    t = Treap()