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):
from bisect import bisect_left, bisect_right, insort_right
class CubeSkipList:
    
    
    def __init__(self, values=None, sorted_=False, cube=100, seed=42):
        
        
        
        
        inf = float("inf")
        self.rand_y = seed
        self.cube = cube
        if values is None:
            self.layer2 = [inf]
            self.layer1 = [[]]
            self.layer0 = [[[]]]
        else:
            self.layer2 = layer2 = []
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l1 = []
            la0 = []
            l0 = []
            for v in values:
                r = rand_depth()
                if r==0:
                    l0.append(v)
                elif r==1:
                    la0.append(l0)
                    l0 = []
                    l1.append(v)
                else:
                    la0.append(l0)
                    layer0.append(la0)
                    layer1.append(l1)
                    l0 = []
                    la0 = []
                    l1 = []
                    layer2.append(v)
            la0.append(l0)
            layer0.append(la0)
            layer1.append(l1)
            layer2.append(inf)

    def rand_depth(self):  
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        if y % self.cube == 0:
            if y % (self.cube ** 2) == 0:
                return 2
            return 1
        return 0

    def add(self, x):  
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        r = self.rand_depth()
        if r==0:
            idx2 = bisect_right(layer2, x)
            idx1 = bisect_right(layer1[idx2], x)
            insort_right(layer0[idx2][idx1], x)
        elif r==1:
            idx2 = bisect_right(layer2, x)
            l1 = layer1[idx2]
            idx1 = bisect_right(l1, x)
            l1.insert(idx1, x)
            la0 = layer0[idx2]
            l0 = la0[idx1]
            idx0 = bisect_right(l0, x)

            la0.insert(idx1+1, l0[idx0:])
            del l0[idx0:]
        else:
            idx2 = bisect_right(layer2, x)
            layer2.insert(idx2, x)
            l1 = layer1[idx2]
            idx1 = bisect_right(l1, x)
            la0 = layer0[idx2]
            l0 = la0[idx1]
            idx0 = bisect_right(l0, x)

            la0.insert(idx1+1, l0[idx0:])
            del l0[idx0:]
            layer0.insert(idx2+1, la0[idx1+1:])
            del la0[idx1+1:]
            layer1.insert(idx2+1, l1[idx1:])
            del l1[idx1:]

    def remove(self, x):  
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        idx2 = bisect_right(layer2, x)
        l1 = layer1[idx2]
        idx1 = bisect_right(l1, x)
        la0 = layer0[idx2]
        l0 = la0[idx1]
        idx0 = bisect_right(l0, x)
        if idx0==len(l0):
            if idx1==len(l1):
                return layer2[idx2]
            return l1[idx1]
        return l0[idx0]

    def search_lower(self, x):  
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        idx2 = bisect_left(layer2, x)
        l1 = layer1[idx2]
        idx1 = bisect_left(l1, x)
        la0 = layer0[idx2]
        l0 = la0[idx1]
        idx0 = bisect_left(l0, x)
        if idx0==0:
            if idx1==0:
                return layer2[idx2-1]
            return l1[idx1-1]
        return l0[idx0-1]

    def pop(self, idx):
        
        
        
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer2)
        print(self.layer1)
        print(self.layer0)


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])
    ssl = CubeSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

Solution (Python):
from bisect import bisect_left, bisect_right, insort_right
class CubeSkipList:
    
    
    def __init__(self, values=None, sorted_=False, cube=100, seed=42):
        
        
        
        
        inf = float("inf")
        self.rand_y = seed
        self.cube = cube
        if values is None:
            self.layer2 = [inf]
            self.layer1 = [[]]
            self.layer0 = [[[]]]
        else:
            self.layer2 = layer2 = []
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l1 = []
            la0 = []
            l0 = []
            for v in values:
                r = rand_depth()
                if r==0:
                    l0.append(v)
                elif r==1:
                    la0.append(l0)
                    l0 = []
                    l1.append(v)
                else:
                    la0.append(l0)
                    layer0.append(la0)
                    layer1.append(l1)
                    l0 = []
                    la0 = []
                    l1 = []
                    layer2.append(v)
            la0.append(l0)
            layer0.append(la0)
            layer1.append(l1)
            layer2.append(inf)

    def rand_depth(self):  
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        if y % self.cube == 0:
            if y % (self.cube ** 2) == 0:
                return 2
            return 1
        return 0

    def add(self, x):  
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        r = self.rand_depth()
        if r==0:
            idx2 = bisect_right(layer2, x)
            idx1 = bisect_right(layer1[idx2], x)
            insort_right(layer0[idx2][idx1], x)
        elif r==1:
            idx2 = bisect_right(layer2, x)
            l1 = layer1[idx2]
            idx1 = bisect_right(l1, x)
            l1.insert(idx1, x)
            la0 = layer0[idx2]
            l0 = la0[idx1]
            idx0 = bisect_right(l0, x)

            la0.insert(idx1+1, l0[idx0:])
            del l0[idx0:]
        else:
            idx2 = bisect_right(layer2, x)
            layer2.insert(idx2, x)
            l1 = layer1[idx2]
            idx1 = bisect_right(l1, x)
            la0 = layer0[idx2]
            l0 = la0[idx1]
            idx0 = bisect_right(l0, x)

            la0.insert(idx1+1, l0[idx0:])
            del l0[idx0:]
            layer0.insert(idx2+1, la0[idx1+1:])
            del la0[idx1+1:]
            layer1.insert(idx2+1, l1[idx1:])
            del l1[idx1:]

    def remove(self, x):  
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        idx2 = bisect_right(layer2, x)
        l1 = layer1[idx2]
        idx1 = bisect_right(l1, x)
        la0 = layer0[idx2]
        l0 = la0[idx1]
        idx0 = bisect_right(l0, x)
        if idx0==len(l0):
            if idx1==len(l1):
                return layer2[idx2]
            return l1[idx1]
        return l0[idx0]

    def search_lower(self, x):  
        layer2, layer1, layer0 = self.layer2, self.layer1, self.layer0
        idx2 = bisect_left(layer2, x)
        l1 = layer1[idx2]
        idx1 = bisect_left(l1, x)
        la0 = layer0[idx2]
        l0 = la0[idx1]
        idx0 = bisect_left(l0, x)
        if idx0==0:
            if idx1==0:
                return layer2[idx2-1]
            return l1[idx1-1]
        return l0[idx0-1]

    def pop(self, idx):
        
        
        
        raise NotImplementedError
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer2)
        print(self.layer1)
        print(self.layer0)


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])
    ssl = CubeSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

Solution (Python):
import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret

    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]

    def dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")


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 = SqrtSet()
    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()

Solution (Python):
import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret

    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]

    def dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")


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 = SqrtSet()
    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()

Solution (Python):
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    
    
    
    
    
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        
        
        
        
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def rand_depth(self):  
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  
        layer1, layer0 = self.layer1, self.layer0
        if self.rand_depth():
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_lower(self, x):  
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  
            return layer1[idx1-1]
        else:
            return layer0_idx1[idx0-1]
        
        
        
        
        
        
        
        
        
        
        
        

    def pop(self, idx):
        
        
        
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


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])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

Solution (Python):

import sys
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
import random
import bisect
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 fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, 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 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) の和'''
        if i < 0:
            return 0
        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 >>= 1
        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)の和を求める
        >>> bit = BIT([1,2,3,4,5])
        >>> bit.query(1,4)
        9
        >>> bit.query(0,2)
        3
        '''
        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])


class sqrtDecomposition():
    def __init__(self, N):
        self.BASE = 1000
        self.size = 0
        self.a = [[] for i in range(ceil(N / self.BASE))]
        self.b = BIT(ceil(N / self.BASE))

    def insert(self, i):
        self.size += 1
        idx = bisect.bisect_left(self.a[i // self.BASE], i)
        self.a[i // self.BASE].insert(idx, i)
        self.b.add(i // self.BASE, 1)
        return (i // self.BASE, idx)

    def _next(self, key, idx1, idx2):
        if key >= self.size:
            return (None, None)
        if len(self.a[idx1]) - 1 == idx2:
            idx = self.b.lower_bound(key + 1)
            return (idx, 0)
        else:
            return (idx1, idx2 + 1)

    def _prev(self, key, idx1, idx2):
        if key <= 0:
            return (None, None)
        if idx2 == 0:
            idx = self.b.lower_bound(key)
            return (idx, len(self.a[idx]) - 1)
        else:
            return (idx1, idx2 - 1)

    def get(self, left, right):
        left += 1
        right += 1
        idx1, idx2 = None, None
        for key in range(left, right):
            
            if key <= 0 or key > self.size:
                yield (None, None)
                continue
            if not idx1:
                idx1 = self.b.lower_bound(key)
                idx2 = key - self.b.sum(idx1) - 1
            else:
                idx1, idx2 = self._next(key - 1, idx1, idx2)
            yield (idx1, idx2)

def main():
    
    
    
    N = ii()
    P = lmi()
    t = sqrtDecomposition(N)
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    
    ans = 0
    for num, i in enumerate(L):
        c = t.insert(i)
        idx = t.b.sum(c[0]) + c[1]
        l = [-1] * 4
        l[1] = t._prev(idx, *c)
        l[0] = t._prev(idx - 1, *l[1])
        l[2] = t._next(idx + 1, *c)
        l[3] = t._next(idx + 2, *l[2])
        
        for j in range(4):
            if l[j][0] is not None:
                l[j] = t.a[l[j][0]][l[j][1]]
            else:
                if j >= 2:
                    l[j] = N
                else:
                    l[j] = -1

        
        ans += (abs(i - l[1]) * abs(l[3] - l[2]) + abs(l[1] - l[0]) * abs(l[2] - i)) * (N - num)
    print(ans)
    return


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
        import cProfile
        cProfile.run('for i in range(100): main()', sort=1)
    else:
        main()