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 collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007



import pprint

class BalancingTree:
    def __init__(self, n = 20):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def __str__(self):
        def debug_info(nd):
            return (nd.value - 1, nd.left.value - 1 if nd.left else None, nd.right.value - 1 if nd.right else None)

        def debug_node(nd):
            v = debug_info(nd) if nd.value else ()
            left = debug_node(nd.left) if nd.left else []
            right = debug_node(nd.right) if nd.right else []
            return [v, left, right]

        return pprint.PrettyPrinter(indent=4).pformat(debug_node(self.root))

    __repr__ = __str__

    def append(self, v):
        v += 1
        nd = self.root
        while True:
            
            if v == nd.value:
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        return self.leftmost(nd.left) if nd.left else nd

    def rightmost(self, nd):
        return self.rightmost(nd.right) if nd.right else nd

    def find_l(self, v): 
        v += 1
        nd = self.root
        prev = nd.value if nd.value < v else 0
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): 
        v += 1
        nd = self.root
        prev = nd.value if nd.value > v else 0
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def max(self):
        return self.find_l((1<<self.N)-1)

    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): 
        v += 1
        if not nd:
            nd = self.root
        if not prev:
            prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    
    def lower_limit(self, v):
        upper = self.find_r(v)
        return self.find_l(upper)

    
    def lower_bound(self, v):
        lower = self.find_l(v)
        return self.find_r(lower)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None


def main():
    N = I()
    P = LI()

    tree = BalancingTree()
    stoi = [None] * (N + 1)

    for i, pi in enumerate(P):
        stoi[pi] = i

    tree.append(stoi[N])
    ans = 0

    for pi in range(1, N)[::-1]:
        i = stoi[pi]
        tree.append(i)
        l = tree.find_l(i)
        r = tree.find_r(i)
        k = (i + 1 if l == -1 else i - l)
        m = (N - i if r == tree.root.value - 1 else r - i)

        ll = tree.find_l(l)
        rr = tree.find_r(r)

        if l == -1:
            j = 0
        else:
            j = l + 1 if ll == -1 else l - ll
        if r == tree.root.value - 1:
            n = 0
        else:
            if rr == tree.root.value - 1:
                n = N - r
            else:
                n = rr - r

        ans += pi * (j * m + k * n)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*(N+1)
        self.b=1<<N.bit_length()-1
    def add(self,a,w):
        x=a
        while(x<=self.N):
            self.bit[x]+=w
            x+=x&-x
    def get(self,a):
        ret,x=0,a-1
        while(x>0):
            ret+=self.bit[x]
            x-=x&-x
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 
    def lowerbound(self,w):
        if w<=0:
            return 0
        x=0
        k=self.b
        while k>0:
            if x+k<=self.N and self.bit[x+k]<w:
                w-=self.bit[x+k]
                x+=k
            k//=2
        return x+1

N=int(input())
P=list(map(int,input().split()))
dic={}
bit=BIT(N)
for i in range(N):
    dic[P[i]]=i+1
dic[0]=0
dic[N+1]=N+1
ans=0
ng=[0,N+1]
for i in reversed(range(1,N+1)):
    bit.add(dic[i],1)
    c=bit.get(dic[i]+1)
    l1,l2=bit.lowerbound(c-1),bit.lowerbound(c-2)
    r1,r2=bit.lowerbound(c+1),bit.lowerbound(c+2)
    S=(l1-l2)*(r1-dic[i])+(r2-r1)*(dic[i]-l1)
    ans+=S*i
print(ans)

Solution (Python):
class SegmentTree():

    def __init__(self, iterable, func, e):
        self.func = func
        self.e = e
        ls = list(iterable)
        self.n = 1 << len(ls).bit_length()
        ls.extend( [self.e] * (self.n - len(ls)) )
        self.data = [self.e] * self.n + ls
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)


N = int(input())
Ps = list(map(lambda c: int(c) - 1, input().split()))

def max_tuple(t1, t2):
    if t1[0] < t2[0]:
        t1, t2 = t2, t1

    if t1[1] > t2[0]:
        return t1
    else:
        return (t1[0], t2[0])

max_two_elems = SegmentTree([(P, -1) for P in Ps], max_tuple, (-1, -1))

ans = 0
for i, P in enumerate(Ps):
    ok = 0
    ng = i + 1
    while ng - ok > 1:
        mid = (ng + ok) // 2
        largest, _ = max_two_elems.folded(i - mid, i + 1)
        if largest == P:
            ok = mid
        else:
            ng = mid
    l_width_1 = ng

    if l_width_1 == i + 1:
        l_width_2 = 0
    else:
        ok = 0
        ng = i - l_width_1 + 1
        while ng - ok > 1:
            mid = (ng + ok) // 2
            _, second_largest = max_two_elems.folded(i - l_width_1 - mid, i + 1)
            if second_largest <= P:
                ok = mid
            else:
                ng = mid
        l_width_2 = ng

    ok = 0
    ng = N - i
    while ng - ok > 1:
        mid = (ng + ok) // 2
        largest, _ = max_two_elems.folded(i, i + mid + 1)
        if largest == P:
            ok = mid
        else:
            ng = mid
    r_width_1 = ng

    if r_width_1 == N - i:
        r_width_2 = 0
    else:
        ok = 0
        ng = N - i - r_width_1
        while ng - ok > 1:
            mid = (ng + ok) // 2
            _, second_largest = max_two_elems.folded(i, i + r_width_1 + mid + 1)
            if second_largest <= P:
                ok = mid
            else:
                ng = mid
        r_width_2 = ng

    
    ans += (l_width_2 * r_width_1 + l_width_1 * r_width_2) * (P + 1)
    
print(ans)

Solution (Python):
import bisect
N=int(input())
P=list(map(int,input().split()))

pos=[-1]*(N+1)

for i in range(N):
  pos[P[i]]=i
  
called=[-1,-1,pos[N],N,N]
ans=0
for i in range(N-1,0,-1):
  hoge=pos[i]
  r=bisect.bisect_left(called,hoge)
  R=called[r]
  RR=called[r+1]
  L=called[r-1]
  LL=called[r-2]
  ans+=i*((RR-R)*(hoge-L)+(L-LL)*(R-hoge))
  called.insert(r,hoge)
  
print(ans)

Solution (Python):




class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def debug(self):
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v): 
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): 
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    if prev == 2**17:
                        return N
                    else:
                        return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    if prev == 2**17:
                        return N
                    else:
                        return prev - 1

    @property
    def max(self):
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): 
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None


import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N = I()
P = LI()

A = []
for i in range(N):
    A.append((P[i],i))

A.sort(reverse=True)

BT = BalancingTree(17)

ans = 0
for i in range(N):
    x,y = A[i]
    BT.append(y)
    a = BT.find_l(y)
    b = BT.find_l(a)
    c = BT.find_r(y)
    d = BT.find_r(c)
    ans += ((a-b)*(c-y) + (d-c)*(y-a)) * x

print(ans)

Solution (Python):
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [-1] * i
            break
        else:
            i *= 2
    return tree

def initialization(tree, a):
    l = len(tree) // 2
    for i in range(l, l + len(a)):
        tree[i] = a[i - l]
    for i in range(l - 1, 0, -1):
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
    return

def update(tree, i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def find(tree, s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = -1
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans = max(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = max(ans, tree[t])
            t = (t - 1) // 2
    return ans

n = int(input())
p = list(map(int, input().split()))
q = [0] * n
tree = make_tree(n)
a = [[-1, -1] for _ in range(n)]
b = [[-1, -1] for _ in range(n)]
update(tree, p[0] - 1, 0)
for i in range(1, n):
    a[i][0] = find(tree, p[i], n - 1)
    if not a[i][0] == -1:
        update(tree, p[a[i][0]] - 1, -1)
        a[i][1] = find(tree, p[i], n - 1)
        update(tree, p[a[i][0]] - 1, a[i][0])
    update(tree, p[i] - 1, i)

initialization(tree, [-1] * n)
update(tree, p[-1] - 1, 0)
for i in range(1, n):
    j = n - i - 1
    b[j][0] = find(tree, p[j], n - 1)
    if not b[j][0] == -1:
        update(tree, p[n - b[j][0] - 1] - 1, -1)
        b[j][1] = find(tree, p[j], n - 1)
        update(tree, p[n - b[j][0] - 1] - 1, b[j][0])
    update(tree, p[j] - 1, i)
    if not b[j][0] == -1:
        b[j][0] = n - b[j][0] - 1
    if not b[j][1] == -1:
        b[j][1] = n - b[j][1] - 1

ans = 0
for i in range(n):
    if p[i] == n:
        continue
    if b[i][0] == -1:
        if not a[i][1] == -1:
            x = (n - i) * (a[i][0] - a[i][1])
        elif not a[i][0] == -1:
            x = (n - i) * (a[i][0] + 1)
    elif a[i][0] == -1:
        if not b[i][1] == -1:
            x = (i + 1) * (b[i][1] - b[i][0])
        elif not b[i][0] == -1:
            x = (i + 1) * (n - b[i][0])
    elif a[i][1] == b[i][1] == -1:
        x = (i - a[i][0]) * (n - b[i][0]) + (b[i][0] - i) * (a[i][0] + 1)
    elif b[i][1] == -1:
        x = (b[i][0] - i) * (a[i][0] - a[i][1]) + (i - a[i][0]) * (n - b[i][0])
    elif a[i][1] == -1:
        x = (i - a[i][0]) * (b[i][1] - b[i][0]) + (b[i][0] - i) * (a[i][0] + 1)
    else:
        x = (i - a[i][0]) * (b[i][1] - b[i][0]) + (b[i][0] - i) * (a[i][0] - a[i][1])
    ans += p[i] * x
    
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic={}
for i in range(n):
    dic[p[i]]=i



class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i-1)

bi=BIT(n+1)
ans=0
for i in range(n)[::-1]:
    bi.add(dic[i+1]+1,i+1)
    
    lsum=bi.get(1,dic[i+1])
    l,r=-1,dic[i+1]
    while r-l>1:
        half=(r+l)//2
        if bi.get(1,half)>=lsum:
            r=half
        else:
            l=half
    l1=r
    l2=-1
    if r!=0:
        lsum=bi.get(1,r-1)
        l,r=-1,r-1
        while r-l>1:
            half=(r+l)//2
            if bi.get(1,half)>=lsum:
                r=half
            else:
                l=half
        l2=r
    
    rsum=bi.get(dic[i+1]+2,n)
    l,r=dic[i+1]+2,n+2
    while r-l>1:
        half=(r+l)//2
        if bi.get(half,n)>=rsum:
            l=half
        else:
            r=half
    
    r1=l
    r2=n+1
    if r!=n+1:
        rsum=bi.get(r1+1,n)
        l,r=r1+1,n+2
        while r-l>1:
            half=(r+l)//2
            if bi.get(half,n)>=rsum:
                l=half
            else:
                r=half
        r2=l
    
    
    
    if i==n-1:
        continue
    if l1+l2==-1:
        ans+=(dic[i+1]+1-l1)*(r2-r1)*(i+1)
    elif r1+r2==2*n+3:
        ans+=(l1-l2)*(r1-dic[i+1]-1)*(i+1)
    elif l2+4==r2:
        ans+=2*(i+1)
    else:
        ans+=((l1-l2)*(r1-dic[i+1]-1)+(dic[i+1]+1-l1)*(r2-r1))*(i+1)
    
    
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self._container = [0] * (n + 1)
        self.depth = n.bit_length()

    def sum(self, i):
        if i == 0:
            return 0
        s = 0
        while i > 0:
            s += self._container[i]
            i -= i & (-i)
        return s

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1


def main():
    n = int(readline())
    p = list(map(int, readline().split()))
    idx = dict()

    for i, x in enumerate(p):
        idx[x] = i + 1

    bt = BinaryIndexTree(n + 2)
    bt.add(n + 2, 2)
    bt.add(1, 2)
    ans = 0

    for num in range(n, 0, -1):
        i = idx[num]
        s = bt.sum(i + 1)
        l1 = bt.lower_bound(s)
        l2 = bt.lower_bound(s - 1)
        r1 = bt.lower_bound(s + 1)
        r2 = bt.lower_bound(s + 2)

        ans += num * (i + 1 - l1) * (r2 - r1)
        ans += num * (r1 - i - 1) * (l1 - l2)
        bt.add(i + 1, 1)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())

    p = [int(i) for i in ipt().split()]

    ip = [0]*(n+1)
    for i,pi in enumerate(p):
        ip[pi] = i
    ans = 0

    os = [-1,-1,n,n]
    for i in range(n,0,-1):
        pl = ip[i]
        j = bisect.bisect_left(os,pl)
        w,x,y,z = os[j-2],os[j-1],os[j],os[j+1]
        ans += i*((x-w)*(y-pl)+(pl-x)*(z-y))
        os.insert(j,pl)

    print(ans)


    return None

if __name__ == '__main__':
    main()

Solution (Python):
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.msb = 1 << (size.bit_length()-1)
    
    def add(self, i, w):
        i += 1
        while i < len(self.data):
            self.data[i] += w
            i += i & -i
    
    def get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            return self.get_sum(i.stop) if i.start is None else self.get_sum(i.stop) - self.get_sum(i.start)
        else:
            return 0 
    
    __setitem__ = add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right

def naive(P):
    def it():
        for i in range(len(P)-1):
            for j in range(i+1,len(P)):
                yield sorted(P[i:j+1])[-2]
    return sum(it())

def solve(P):

    def it():
        bit = BinaryIndexedTree(len(P))
        for cnt, (v,i) in enumerate(sorted(((v,i) for i,v in enumerate(P)), reverse=True)):
            bit[i] += 1
            c = bit.get_sum(i)
            low1 = -1 if c <= 0 else bit.bisect_left(c)
            low2 = -1 if c <= 1 else bit.bisect_left(c-1)
            up1 = len(P) if c > cnt-1 else bit.bisect_left(c+2)
            up2 = len(P) if c > cnt-2 else bit.bisect_left(c+3)
            yield v*((up1-i)*(low1-low2)+(i-low1)*(up2-up1))
    return sum(it())


if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    print(solve(P))

Solution (Python):

class BinaryIndexedTree:
    def __init__(self, size):
        size = 1 << (size-1).bit_length()
        self.data = [0] * (size+1)
        self.size = size
    
    def add(self, i, w):
        i += 1
        while i <= self.size:
            self.data[i] += w
            i += i & -i

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

    __getitem__ = sum

    def lower_bound(self, v):
        """
        return smallest i such that v < sum(data[:i])
        """

        s,pos = 0,0
        N = self.size
        k = N
        while k > 0:
            i = pos+k
            if i <= N:
                x = s+self.data[i]
                if x < v:
                    s = x
                    pos = i
            k >>= 1
        return pos


def naive(P):
    def it():
        for i in range(len(P)-1):
            for j in range(i+1,len(P)):
                yield sorted(P[i:j+1])[-2]
    return sum(it())

def solve(P):

    def it():
        bit = BinaryIndexedTree(len(P))
        for cnt, (v,i) in enumerate(sorted(((v,i) for i,v in enumerate(P)), reverse=True)):
            bit.add(i,1)
            c = bit.sum(i)
            
            low1 = -1 if c <= 0 else bit.lower_bound(c)
            low2 = -1 if c <= 1 else bit.lower_bound(c-1)
            up1 = len(P) if c > cnt-1 else bit.lower_bound(c+2)
            up2 = len(P) if c > cnt-2 else bit.lower_bound(c+3)
            yield v*((up1-i)*(low1-low2)+(i-low1)*(up2-up1))
    return sum(it())


if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    print(solve(P))

Solution (Python):
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n = int(input())
    P = list(map(int, input().split()))
    ans = 0
    arr = [[P[i], i] for i in range(n)]
    arr.sort(key=lambda x: -x[0])
    seg = SegTree(0, n, [0]*n)
    for v, idx in arr:
        seg.update(idx, 1)
        if idx < n-1 and seg.query(idx+1, n) > 0:
            L, R = idx, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) < 1:
                    L = M
                else:
                    R = M
            x = R
            L, R = x, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) < 2:
                    L = M
                else:
                    R = M
            r_range = R - x
            L, R = -1, idx
            while L+1 < R:
                M = (L+R+1)//2
                if seg.query(M, idx) == 0:
                    R = M
                else:
                    L = M
            l_range = idx - L
            ans += v * l_range * r_range
            
        if 0 < idx and seg.query(0, idx) > 0:
            L, R = idx, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) == 0:
                    L = M
                else:
                    R = M
            r_range = R - idx
            L, R = 0, idx
            while L+1 < R:
                M = (L+R)//2
                if seg.query(M, idx) < 1:
                    R = M
                else:
                    L = M
            x = L
            L, R = -1, x
            while L+1 < R:
                M = (L+R+1)//2
                if seg.query(M, idx) < 2:
                    R = M
                else:
                    L = M
            l_range = x - L
            ans += v * l_range * r_range
            
        
    print(ans)

if __name__ == "__main__":
    main()