Problem:
 Score: 500 points    Problem Statement  Given is a permutation P of \{1, 2, \ldots, N\} .  For a pair (L, R) (1 \le L \lt R \le N) , let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R .  Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R} .      Constraints   2 \le N \le 10^5  1 \le P_i \le N  P_i \neq P_j  (i \neq j)  All values in input are integers.         Input  Input is given from Standard Input in the following format:  N  P_1  P_2  \ldots  P_N       Output  Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R} .        Sample Input 1 3
2 3 1      Sample Output 1 5  X_{1, 2} = 2, X_{1, 3} = 2 , and X_{2, 3} = 1 , so the sum is 2 + 2 + 1 = 5 .       Sample Input 2 5
1 2 3 4 5      Sample Output 2 30       Sample Input 3 8
8 2 7 3 4 5 6 1      Sample Output 3 136

Solution (Python):

import sys
from bisect import bisect_left, bisect_right
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
from random import shuffle
import cProfile
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 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()



class Avltree:
    """
    AVL木

    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """

    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"

    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node  
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None

    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans

    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans


    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key

    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.key


    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self  
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self, p, v):  
        if p.left == self:
            p.left = v
        else:
            p.right = v
    def insert(self, key):  
        if self.key is None:  
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self, key)
        else:  
            pass  
    def insertx(self, p, key):  
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    node = node.left
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    node = node.right
                    break
                else:
                    node = node.right
        while len(s) != 0:
            node, direct = s.pop()
            if len(s) != 0:
                par = s[-1][0]
            else:
                par = p
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(par, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(par, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(par, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(par, node.SingleLeftRotation())
                    break

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key

def bin_tree_to_list(root):
    """
    type root: root class
    """
    if not root:
        return root
    root = bin_tree_to_list_util(root)
    while root.left:
        root = root.left
    return root

def bin_tree_to_list_util(root):
    if not root:
        return root
    if root.left:
        left = bin_tree_to_list_util(root.left)
        while left.right:
            left = left.right
        left.right = root
        root.left = left
    if root.right:
        right = bin_tree_to_list_util(root.right)
        while right.left:
            right = right.left
        right.left = root
        root.right = right
    return root

def print_tree(root):
    while root:
        print(root.key, end=" ")
        root = root.right
    print()

def binary_tree_paths(root):
    res = []
    if root is None:
        return res
    dfs(res, root, str(root.key))
    return res

def dfs(res, root, cur):
    if root.left is None and root.right is None:
        res.append(cur)
    if root.left:
        dfs(res, root.left, cur + '->' + str(root.left.key))
    if root.right:
        dfs(res, root.right, cur + '->' + str(root.right.key))




def main():
    N = ii()
    P = lmi()
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    
    ans = 0
    rb = Avltree()
    for num, i in enumerate(L):
        rb.insert(i)
        l1 = rb.search_lower(i, -1)
        l2 = rb.search_lower(l1, -1)
        r1 = rb.search_higher(i, N)
        r2 = rb.search_higher(r1, N)
        debug(l2, l1, r1, r2)
        ans += (abs(i - l1) * abs(r2 - r1) + abs(l1 - l2) * abs(r1 - i)) * (N - num)
    print(ans)

    
    
    
    
    
    
    return



if __name__ == '__main__':
    
    main()

Solution (Python):

import sys

INF = float("inf")


class MaxBit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = max(s, self.tree[i])
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = max(self.tree[i], x)
            i += i & -i


class MinBit:
    def __init__(self, n):
        self.size = n
        self.tree = [n-1] * (n + 1)

    def sum(self, i):
        s = self.size-1
        while i > 0:
            s = min(s, self.tree[i])
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = min(self.tree[i], x)
            i += i & -i


def solve(N: int, P: "List[int]"):

    prev = MaxBit(N+2)
    foll = MinBit(N+2)
    seq = [0]*(N+2)

    inv = {p: i for i, p in enumerate(P)}
    
    

    ans = 0
    for i in range(N, 0, -1):
        prev.add(inv[i]+2, inv[i]+1)
        foll.add(N-inv[i]+1, inv[i]+1)
        seq[inv[i]+1] = i

        
        
        
        
        
        p = prev.sum(inv[i]+1)
        pp = prev.sum(p)
        f = foll.sum(N-inv[i])
        ff = foll.sum(N-f+1)
        
        if p > 0:
            
            ans += i*(p-pp)*(f-(inv[i]+1))
            
            
        
        if f < N+1:
            
            ans += i*(inv[i]+1 - p) * (ff - f)
            
            
    print(ans)
    

    
    
    
    
    
    
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    P = [int(next(tokens)) for _ in range(N)]  
    solve(N, P)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
aa = list(map(int, input().split()))
ans = 0
pos = [0] * (n + 1)

for i, a in enumerate(aa):
    pos[a] = i + 2
Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
for a in range(1,n + 1):
    i = pos[a]
    l0 = Lnext[i]
    l1 = Lnext[l0]
    r0 = Rnext[i]
    r1 = Rnext[r0]
    ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
    Lnext[r0] = l0
    Rnext[l0] = r0
print(ans)

Solution (Python):
import sys

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 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




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] の和'''
        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 //= 2
        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)の和を求める'''
        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])




def compress(v):
    sort_v = list(set(v))
    sort_v.sort()
    return sort_v
def dictionary(v):
    res = dict()
    for i in range(len(v)):
        res[v[i]] = i
    return res



def AOJ_ALDS_1_5_D():
    """https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_D"""
    n = ii()
    a = lmi()
    bit = BIT(n)
    ans = 0
    mp = dictionary(compress(a))
    for j in range(n):
        ans += j - bit.sum0(mp[a[j]])
        bit.add0(a[j], 1)
    print(ans)



def AOJ_DSL2B():
    """https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B"""
    n, q = mi()
    bit = BIT(n, 0)
    for _ in range(q):
        c, x, y = mi()
        if c == 0:
            bit.add(x, y)
        elif c == 1:
            print(bit.query(x, y + 1))



def ARC033_C():
    q = ii()
    bit = BIT(200000, 0)
    for _ in range(q):
        t, x = mi()
        if t == 1:
            bit.add(x, 1)
        elif t == 2:
            k = bit.lower_bound(x)
            bit.add(k, -1)
            print(k)





def ABC140_E():
    '''https://atcoder.jp/contests/abc140/tasks/abc140_e'''
    N = ii()
    P = lmi()
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    ans = 0
    bit = BIT(N)
    for num, i in enumerate(L):
        bit.add(i, 1)
        
        x = bit.sum(i)
        l2 = bit.getKthNum(x - 2)
        l1 = bit.getKthNum(x - 1)
        r1 = bit.getKthNum(x + 1)
        r2 = bit.getKthNum(x + 2)
        debug(x, l2, l1, r1, r2)
        ans += (abs(r2 - r1) * abs(i - l1) + abs(l1 - l2) * abs(r1 - i)) * (N - num)
    print(ans)


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
    
    
    
    ABC140_E()

Solution (Python):
import sys

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 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




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) の和'''
        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):
        '''sum(i)>=w をみたす最小の index'''
        if w <= 0:
            return 0
        x = 0
        k = 1 << (self.size.bit_length() - 1)
        while k > 0:
            if x + k <= self.size and self.tree[x + k] < w:
                w -= self.tree[x + k]
                x += k
            k //= 2
        return x + 1

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

    def query(self, l, r):
        '''[l, r)の和を求める'''
        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])




def compress(v):
    sort_v = list(set(v))
    sort_v.sort()
    return sort_v
def dictionary(v):
    res = dict()
    for i in range(len(v)):
        res[v[i]] = i
    return res



def AOJ_ALDS_1_5_D():
    """https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_D"""
    n = ii()
    a = lmi()
    bit = BIT(n)
    ans = 0
    mp = dictionary(compress(a))
    for j in range(n):
        ans += j - bit.sum0(mp[a[j]])
        bit.add0(a[j], 1)
    print(ans)



def AOJ_DSL2B():
    """https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B"""
    n, q = mi()
    bit = BIT(n, 0)
    for _ in range(q):
        c, x, y = mi()
        if c == 0:
            bit.add(x, y)
        elif c == 1:
            print(bit.query(x, y + 1))



def ARC033_C():
    q = ii()
    bit = BIT(200000, 0)
    for _ in range(q):
        t, x = mi()
        if t == 1:
            bit.add(x, 1)
        elif t == 2:
            k = bit.bisect_left(x)
            bit.lower_bound(k, -1)
            print(k)





def ABC140_E():
    N = ii()
    P = lmi()
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    ans = 0
    bit = BIT(N)
    for num, i in enumerate(L):
        bit.add(i, 1)
        
        x = bit.sum(i)
        l2 = bit.lower_bound(x - 1) - 1
        l1 = bit.lower_bound(x) - 1
        r1 = bit.upper_bound(x + 1)
        r2 = bit.upper_bound(x + 2)
        debug(x, l2, l1, r1, r2)
        ans += (abs(r2 - r1) * abs(i - l1) + abs(l1 - l2) * abs(r1 - i)) * (N - num)
    print(ans)


if __name__ == '__main__':
    
    
    
    ABC140_E()

Solution (Python):

N=int(input())
p=list(map(int,input().split()))
LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]
E = [(v, i+1) for i, v in enumerate(p)]
E.sort()
ans=0
for v, i in E:
  r0 = RR[i]
  r1 = RR[r0]
  l0 = LL[i]
  l1 = LL[l0]
  RR[l0] = r0
  LL[r0] = l0

  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *


class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

    
    def upper_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if x < y:
                r = m
            else:
                l = m
        return r

    
    def lower_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if y < x:
                l = m
            else:
                r = m
        return r

N = int(input())
P = [int(x) for x in input().split()]
I = [0] * (N+1)
for i, x in enumerate(P, 1):
    I[x] = i
bit = BIT(N+1)
bit.add(I[N], 1)
ans = 0
for x in range(N-1, 0, -1):
    s = bit.sum(I[x])
    l = bit.lower_bound(s)
    r = bit.upper_bound(s)
    ans += x*((bit.upper_bound(s+1)-r)*(I[x]-l)+(l-bit.lower_bound(s-1))*(r-I[x]))
    bit.add(I[x], 1)
print(ans)

Solution (Python):
INF = 10**9

class RmQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data_min = [INF] * (2*self.size-1)
        self.initialize(a)

    
    def initialize(self, a):
        for i in range(self.n):
            self.data_min[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data_min[i] = min(self.data_min[i*2 + 1], self.data_min[i*2 + 2])

    
    def update(self, k, x):
        k += self.size - 1
        self.data_min[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data_min[k] = min(self.data_min[2*k+1], self.data_min[2*k+2])

    
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data_min[R-1])
            if L & 1:
                s = min(s, self.data_min[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data_max = [-INF] * (2*self.size-1)
        self.initialize(a)

    
    def initialize(self, a):
        for i in range(self.n):
            self.data_max[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data_max[i] = max(self.data_max[i*2 + 1], self.data_max[i*2 + 2])

    
    def update(self, k, x):
        k += self.size - 1
        self.data_max[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data_max[k] = max(self.data_max[2*k+1], self.data_max[2*k+2])

    
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = -INF 
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data_max[R-1])
            if L & 1:
                s = max(s, self.data_max[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n = int(input())
a = [int(item) for item in input().split()]
indexes = [0] * n
for i, item in enumerate(a):
    indexes[item - 1] = i
indexes.reverse()

a_min = [-1] * 2 + [INF] * n + [n] * 2
a_max = [-1] * 2 + [-INF] * n + [n] * 2
rMq = RMQ(a_max)
rmq = RmQ(a_min)
ans = 0
for i, idx in enumerate(indexes):
    num = n - i
    L1 = rMq.query(0, idx+2)
    L2 = rMq.query(0, L1+2)
    R1 = rmq.query(idx+2, n+4)
    R2 = rmq.query(R1+3, n+4)
    ans += (L1 - L2) * (R1 - idx) * num 
    ans += (idx - L1) * (R2 - R1) * num 
    rMq.update(idx+2, idx)
    rmq.update(idx+2, idx)
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()
    print(n**3)
    return


def B():
    n = I()
    a = LI()
    b = LI()
    c = LI()
    ans = sum(b)
    for i in range(n-1):
        x = a[i]
        y = a[i+1]
        if y == x+1:
            ans += c[x-1]
    print(ans)
    return


def C():
    n = I()
    b = LI()
    b.append(float("inf"))
    a = [min(b[i],b[i-1]) for i in range(n)]
    print(sum(a))
    return


def D():
    n,k = LI()
    a = S()
    ans = 0
    for i in range(n-1):
        if a[i] == a[i+1]:
            ans += 1
    print(min(n-1,ans+2*k))
    return


def E():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n = I()
    p = LI()
    p = [(p[i],i+2) for i in range(n)]
    p.sort(key = lambda x:-x[0])
    bit = [0]*(n+3)
    add(p[0][1])
    ans = 0
    for pi,i in p[1:]:
        s = sum(i)
        l = 0
        r = i
        while r-l > 1:
            m = (l+r)>>1
            if sum(m) == s:
                r = m
            else:
                l = m
        x1 = r

        l = i
        r = n+2
        while r-l > 1:
            m = (l+r)>>1
            if sum(m) == s:
                l = m
            else:
                r = m
        x2 = r

        s_ = s-1
        l = 0
        r = x1
        while r-l > 1:
            m = (l+r)>>1
            if sum(m) == s_:
                r = m
            else:
                l = m
        x3 = r

        s_ = s+1
        l = x2
        r = n+2
        while r-l > 1:
            m = (l+r)>>1
            if sum(m) == s_:
                l = m
            else:
                r = m
        x4 = r
        ans += pi*((x1-x3)*(x2-i)+(x4-x2)*(i-x1))
        add(i)
    print(ans)
    return


def F():
    n = I()
    s = LI()
    s.sort()
    s = s[::-1]
    m = 1<<n
    f = [-1]*m
    f[0] = 0
    for i in range(n):
        k = 0
        l = 0
        for j in range(1<<i):
            while f[k] != i:
                k += 1
            while f[l] >= i or s[k] <= s[l]:
                l += 1
                if l == m:
                    print("No")
                    return
            f[l] = i+1
            k += 1
        for j in range(m):
            if f[j] >= 0:
                f[j] = i+1
    print("Yes")
    return


if __name__ == "__main__":
    E()

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

    def add(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        total = 0
        while i > 0:
            total += self.data[i]
            i -= i&-i
        return total

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

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

index = [0] * (n+1)

for i in range(n):
    index[p[i]] = i+1

used = BIT(n)
result = 0
for i in range(1, n+1)[::-1]:
    x = index[i]
    if used.len() == 0:
        used.add(x, 1)
        continue
    dx = used.sum(x)
    
    if dx > 0:
        lbl = 1
        if dx > 1:
            lbl = used.search(dx-1)+1
        lbr = used.search(dx)
        rbl = n
        if used.len() != dx:
            rbl = used.search(dx+1) -1
        result += (lbr-lbl+1) * (rbl-x+1) * i
    
    if dx < used.len():
        rbr = n
        if dx < used.len() -1:
            rbr = used.search(dx+2)-1
        rbl = used.search(dx+1)
        lbr = 1
        if dx > 0:
            lbr = used.search(dx) +1
        result += (rbr-rbl+1) * (x-lbr+1) * i
    used.add(x, 1)
 
print(result)

Solution (Python):
N = int(input())
P = list(map(int, input().split()))
LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]

E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

res = 0
for v, i in E:
  
  
  
  
  
  
  
  
  
  l0 = LL[i]; l1 = LL[l0]
  r0 = RR[i]; r1 = RR[r0]
  
  
  LL[RR[i]], RR[LL[i]] = LL[i], RR[i]

  res += ((r1 - r0) * (i - l0) + (r0 - i) * (l0 - l1)) * v
print(res)

Solution (Python):
N = int(input())
P = [int(x) for x in input().split()]
L = [0] * (N + 2)
R = [N + 1] * (N + 2)
I = list(range(N + 1))
for i in range(N):
  I[P[i]] = i
ans = 0
ST = [0] * (N + 2)
def cnt(i):
  ret = 0
  while i:
    ret += ST[i]
    i -= i & (-i)
  return ret
def update(i):
  while i <= N + 1:
    ST[i] += 1
    i += i & (-i)
def ls(idx):
  b = cnt(idx)
  if b == 0:
    return 0
  s = 0
  t = idx
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) < b:
      s = m
    else:
      t = m
  return t
def rs(idx):
  b = cnt(idx)
  s = idx
  t = N + 1
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) > b:
      t = m
    else:
      s = m
  return t
for i in range(N, 0, -1):
  index = I[i]
  idx = index + 1
  L[idx] = ls(idx)
  R[idx] = rs(idx)
  L[R[idx]] = idx
  R[L[idx]] = idx
  update(idx)
  ans += i * ((idx - L[idx]) * (R[R[idx]] - R[idx]) + (L[idx] - L[L[idx]]) * (R[idx] - idx))
print(ans)