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

class Node:
    def __init__(self, key, height):
        self.key = key 
        self.height = height 
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): 
        return self.size(self.left) - self.size(self.right)

    
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None 
        self.change = False 

    
    
    
    def rotateL(self, n): 
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): 
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    
    
    
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): 
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    
    
    

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 
 
    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    L, R = dict(), dict()
    for i, p in enumerate(P): pindex[p - 1] = i 
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])

    if N == 10 ** 5:
        for i in range(N-2, 0, -1):
            pid = pindex[i]
            left, right = T.lower_bound(pid, -1), T.upper_bound(pid, N)
            if left == -1: l2 = -1
            else: l2 = T.lower_bound(left, -1)
            if right == N: r2 = N
            else: r2 = T.upper_bound(right, N)
            Ans += (i + 1) * ((pid - left) * (r2 - right) + (right - pid) * (left - l2))
            T.insert(pid)
        Ans += (2 if 0 < pindex[0] < N - 1 else 1)

    else:
        L[pindex[N-1]] = -1
        R[pindex[N-1]] = N
        L[-1] = L[N] = -1
        R[-1] = R[N] = N    
        for i in reversed(range(N-1)):
            pid = pindex[i]
            L[pid], R[pid] = l, r = T.search(pid, -1, N)
            Ans += (i + 1) * ((pid - l) * (R[r] - r) + (r - pid) * (l - L[l]))
            T.insert(pid)
            R[l] = L[r] = pid

    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):



class SegTree():
    def __init__(self, N, e=0, operator_func=lambda x,y:x+y):
        self.e = e

        self.N = N
        bitlen = (N).bit_length()
        self.size = 2**(bitlen if N&(N-1) else bitlen-1)
        self.node = [self.e] * (2*self.size)
        self.op = operator_func

    def set_list(self, l):
        for i,j in enumerate(l):
            self.node[i+self.size-1] = j
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

    def bisect_left(self, x):
        if x > self.node[0]:
            return self.N
        p, ans = 0, 0
        node_size = 2 * self.size - 1
        x -= 1

        while p < node_size:
            ans = p - (self.size - 1)
            p1, p2 = 2 * p + 1, 2 * p + 2

            if p1 < node_size and self.node[p1] <= x:
                x -= self.node[p1]
                p = p2
            else:
                p = p1
        
        return ans+1


if __name__ == "__main__":
    
    N = int(input())
    l = [(j, i) for i, j in enumerate(map(int, input().split()))]
    l.sort(key=lambda x:-x[0])
    tree = SegTree(N)
 
    ans = 0
 
    for n, (value, idx) in enumerate(l, start=1):
        v = tree.get(0, idx + 1)
        a = tree.bisect_left(v - 1) if v > 1 else 0
        b = tree.bisect_left(v - 0) if v else 0
        c = tree.bisect_left(v + 1) if n-v>1 else N+1
        d = tree.bisect_left(v + 2) if n-v>2 else N+1
 
        tree.update(idx, 1)
        idx += 1
        ans += ((b-a)*(c-idx)+(d-c)*(idx-b)) * value
 
    print(ans)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.dat = [0]*n

    def add(self, k, a):
        while k < self.n:
            self.dat[k] += a
            k |= k+1
 
    def sum(self, k):
        s = 0
        while k >= 0:
            s += self.dat[k]
            k = (k & (k+1)) - 1
        return s

N = int(input())
P = [int(x) for x in input().split()]

pos = [0]*(N+1)
for i in range(N):
    pos[P[i]] = i

bit = BIT(N)
ans = 0
for i in range(N, 0, -1):
    bit.add(pos[i], 1)
    s = bit.sum(pos[i])
    bound = []
    for s2 in [s-2, s-1, s+1, s+2]:
        if s2 <= 0:
            bound.append(-1)
            continue
        
        ok, ng = N, -1
        while ok-ng>1:
            mid = (ok+ng)>>1
            if bit.sum(mid) >= s2:
                ok = mid
            else:
                ng = mid
        bound.append(ok)
    res = (bound[1]-bound[0])*(bound[2]-pos[i]) + (pos[i]-bound[1])*(bound[3]-bound[2])
    ans += i*res

print(ans)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth + 1)[::-1]:
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


N = int(input())
l = [(j, i) for i, j in enumerate(map(int, input().split()))]
l.sort(key=lambda x:-x[0])
tree = BIT(N)
m = [0]*N
ans = 0

for value, idx in l:
    v = tree.sum(idx + 1)

    a = tree.lower_bound(v - 1)[0] if v>1 else 0
    b = tree.lower_bound(v - 0)[0] if v else 0
    c = tree.lower_bound(v + 1)[0] 
    d = tree.lower_bound(v + 2)[0]

    tree.add(idx + 1, 1)
    idx += 1
    ans += ((b-a)*(c-idx)+(d-c)*(idx-b)) * value

print(ans)

Solution (Python):
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        
        n = 2 ** (A - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        
        
        
        
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree(N, max, -1)
    minSeg = SegmentTree(N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()

Solution (Python):
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        
        n = A
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        
        
        
        
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree(N, max, -1)
    minSeg = SegmentTree(N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()

Solution (Python):
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        
        
        
        
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree([-1] * N, max, -1)
    minSeg = SegmentTree([N] * N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()

Solution (Python):


class BIT:
    def __init__(self, n, init_list):
        self.num = n+1
        self.tree = [0]*self.num
        for i,e in enumerate(init_list):
            self.update(i,e)

    def update(self,k,x):
        k = k+1
        while k < self.num:
            self.tree[k] += x
            k += (k&(-k))
        return 
    
    
    def query(self, l,r):
        ret = 0
        while r>0:
            ret += self.tree[r]
            r -= r&(-r)
        while l>0:
            ret -= self.tree[l]
            l -= l&(-l)
        
        return ret


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

idxlist = [0]*N
for i,a in enumerate(A):
    idxlist[a-1] = i+2

A = [N+1]*2 + A + [N+1]*2

ans = 0
seg = BIT(N+4,[1]*2+[0]*N+[1]*2)

def judge(l,r,key):
    if l>r:
        l,r = r,l
    res = seg.query(l,r+1)
    if res>key:
        return False
    else:
        return True

def bsearch(idx,ng,key):
    ok = idx
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if judge(idx,mid,key):
            ok = mid
        else:
            ng = mid
    return ng


for idx in reversed(idxlist):
    if A[idx]==N:
        seg.update(idx,1)
        continue
    ng_l = 0
    ng_r = N+3
    
    L1 = bsearch(idx,ng_l,0)
    L2 = bsearch(idx,ng_l,1)
    R1 = bsearch(idx,ng_r,0)
    R2 = bsearch(idx,ng_r,1)
    
    coef = 0
    if A[L1]!=N+1:
        coef += (L1-L2)*(R1-idx)
    if A[R1]!=N+1:
        coef += (R2-R1)*(idx-L1)
    ans += A[idx]*coef
    seg.update(idx,1)
    
print(ans)

Solution (Python):



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

n=int(input())
arr=list(map(int,input().split()))
arr2=[[arr[i],i+1] for i in range(n)]
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
avl=Avltree()
ans=0
avl.insert(0)
avl.insert(n+1)
for val,pos in arr2:
  fl=avl.search_lower(pos,0)
  if fl==0:
    sl=0
  else:
    sl=avl.search_lower(fl,0)
  fr=avl.search_higher(pos,n+1)
  if fr==n+1:
    sr=n+1
  else:
    sr=avl.search_higher(fr,n+1)
  cnt=(fl-sl)*(fr-pos)+(pos-fl)*(sr-fr)
  ans+=cnt*val
  avl.insert(pos)
print(ans)

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)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if res != x:  
            if layer0_idx1:
                idx0 = bisect_left(layer0_idx1, x)
                if idx0 != 0:
                    return layer0_idx1[idx0-1]
            return layer1[idx1-1]  
        else:
            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)

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

D = {P[i]:i+1 for i in range(N)}
ans = 0

L = SquareSkipList()
L.add(D[N])

for i in range(1,N)[::-1]:
    l = L.search_lower(D[i])
    h = L.search_higher(D[i])
    if l == float('inf'):
        hh = L.search_higher(h)
        if hh == float('inf'):
            hh = N+1
        ans += (D[i]*(hh-h))*i
    elif h == float('inf'):
        ll = L.search_lower(l)
        if ll == float('inf'):
            ll = 0
        ans += ((N+1-D[i])*(l-ll))*i
    else:
        hh = L.search_higher(h)
        if hh == float('inf'):
            hh = N+1
        ll = L.search_lower(l)
        if ll == float('inf'):
            ll = 0
        ans += ((h-D[i])*(l-ll)+(D[i]-l)*(hh-h))*i
    L.add(D[i])
    
print(ans)

Solution (Python):
N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)

Solution (Python):
class BIT:
  
  def __init__(self, N):
    self.n = N
    self.tree = [0]*(self.n+1)
    
  def bsum(self, i):
    s = 0
    while i:
      s += self.tree[i]
      i -= i&(-i)
    return s
  
  def badd(self, i, x):
    while i<=self.n:
      self.tree[i] += x
      i += i&(-i)
  
  def bsearch(self, x):
    i = 0
    s = 0
    step = 1<<(self.n.bit_length()-1)
    while step:
      if i+step<=self.n and s+self.tree[i+step]<x:
        i += step
        s += self.tree[i]
      step >>= 1
    return i+1

      
N = int(input())
P = [0]+[int(c) for c in input().split()]

ntoi = [0]*(N+1)
for i in range(N+1):
  ntoi[P[i]] = i

bit = BIT(N)

ans = 0
for m in range(N, 0, -1):
  I = ntoi[m]
  L = bit.bsum(I)
  bit.badd(I,1)
  R = N-L-m
  a = bit.bsearch(L-1) if L>1 else 0
  b = bit.bsearch(L) if L>0 else 0
  c = bit.bsearch(L+2) if R>0 else N+1
  d = bit.bsearch(L+3) if R>1 else N+1
  coef = 0
  if b!=0:
    coef += (b-a)*(c-I)
  if c!=0:
    coef += (I-b)*(d-c)
  ans += m*coef

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): 
        return self.sum(j - 1) - self.sum(i - 1)

    def search(self, k):
        if k > self.total or k <= 0:
            return -1
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        
        
        
        return now_index

n = I()
P = LI()
val_idx = {P[j]:j+1 for j in range(n)}
bit = BIT(n + 2)
bit.add(n + 1, 1)
bit.add(0, 1)
ans = 0
for k in range(n, 0, -1):
    idx = val_idx[k]
    m = bit.sum(idx)
    l1 = bit.search(m - 1)
    l2 = bit.search(m)
    r1 = bit.search(m + 1)
    r2 = bit.search(m + 2)
    if l1 >= 0:
        ans += (l2 - l1) * (r1 - idx) * k
    if r2 >= 0:
        ans += (idx - l2) * (r2 - r1) * k
    bit.add(idx, 1)

print(ans)