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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """
    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok


def calc1(m):
    cnt = lend - bit.sum(m-1)
    return cnt == 0


def calc2(m):
    cnt = lend - bit.sum(m-1)
    return cnt <= 1


def calc3(m):
    cnt = bit.sum(m) - rstart
    return cnt == 0


def calc4(m):
    cnt = bit.sum(m) - rstart
    return cnt <= 1

N = INT()
A = LIST()

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

bit = BIT(N+2)

bit.add(0, 2)
bit.add(N+1, 2)
ans = [0] * (N+1)

for a in range(N, 0, -1):
    
    idx = idxs[a]
    
    lend = bit.sum(idx)
    rstart = bit.sum(idx-1)
    
    p = bisearch_min(0, idx+1, calc2)
    
    q = bisearch_min(0, idx+1, calc1)
    
    r = bisearch_max(idx, N+1, calc3)
    
    s = bisearch_max(idx, N+1, calc4)
    
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    
    bit.add(idx, 1)

print(sum(ans))

Solution (Python):
import sys,bisect as bs,collections as cl
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

p = [0] + l() + [n+1]
ans = 0
a = [0 for i in range(n+2)]

for i in range(n+2):
    a[p[i]] = i

l = [set() for i in range(n+2)]
r = [set() for i in range(n+2)]

for i in range(n+2):
    l[i].add(max(0,i-1))
    l[i].add(max(0,i-2))
    r[i].add(min(n+1,i+1))
    r[i].add(min(n+1,i+2))


for i in range(n+1):
    m = a[i]
    x2,x1,y1,y2 = min(l[m]),max(l[m]),min(r[m]),max(r[m])
    hoge= i*(abs((m-x1)*(y2-y1)) + abs((y1-m)*(x1-x2)))
    ans += hoge

    r[x1].clear()
    r[x1].add(y1)
    r[x1].add(y2)

    l[y1].clear()
    l[y1].add(x1)
    l[y1].add(x2)
    
    r[x2].clear()
    r[x2].add(x1)
    r[x2].add(y1)

    l[y2].clear()
    l[y2].add(y1)
    l[y2].add(x1)
    

print(ans)

Solution (Python):
import sys,bisect as bs,collections as cl
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

p = [0] + l() + [n+1]
ans = 0
a = [0 for i in range(n+2)]

for i in range(n+2):
    a[p[i]] = i

l = [set() for i in range(n+2)]
r = [set() for i in range(n+2)]

for i in range(n+2):
    l[i].add(max(0,i-1))
    l[i].add(max(0,i-2))
    r[i].add(min(n+1,i+1))
    r[i].add(min(n+1,i+2))


for i in range(n+1):
    m = a[i]
    x2,x1,y1,y2 = min(l[m]),max(l[m]),min(r[m]),max(r[m])
    hoge= i*(abs((m-x1)*(y2-y1)) + abs((y1-m)*(x1-x2)))
    ans += hoge

    r[x1].clear()
    r[x1].add(y1)
    r[x1].add(y2)

    l[y1].clear()
    l[y1].add(x1)
    l[y1].add(x2)
    
    r[x2].clear()
    r[x2].add(x1)
    r[x2].add(y1)

    l[y2].clear()
    l[y2].add(y1)
    l[y2].add(x1)
    

print(ans)

Solution (Python):





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

In = [0] * (N+1)
for i in range(N):
  In[Pn[i]] = i+1

cnt = 0
l = [0] + [i for i in range(N+1)]
r = [i+1 for i in range((N+1))] + [N+1]

for v in range(1, N+1):
  i = In[v]
  
  l1 = l[i]
  l2 = l[l1]
  r1 = r[i]
  r2 = r[r1]
  cnt += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * v
  
  l[r1] = l1
  r[l1] = r1
    
print(cnt)

Solution (Python):
import sys,bisect as bs,collections as cl
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

p = [0] + l() + [n+1]
ans = 0
a = [0 for i in range(n+2)]

for i in range(n+2):
    a[p[i]] = i
l1 = [max(0,i-1) for i in range(n+2)]
l2 = [max(0,i-2) for i in range(n+2)]
r1 = [min(n+1,i+1) for i in range(n+2)]
r2 = [min(n+1,i+2) for i in range(n+2)]


for i in range(n+1):
    m = a[i]
    x2,x1,y1,y2 = l2[m],l1[m],r1[m],r2[m]
    hoge= i*(abs((m-x1)*(y2-y1)) + abs((y1-m)*(x1-x2)))
    ans += hoge
    
    r1[x1] = y1
    r2[x1] = y2
    
    l1[y1] = x1
    l2[y1] = x2
    
    r1[x2] = x1
    r2[x2] = y1
    
    l1[y2] = y1
    l2[y2] = x1
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    n = int(input()[:-1])
    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)

main()

Solution (Python):
n = int(input())
lst = list(enumerate(list(map(int, input().split()))))
 
sorted_lst = sorted(lst, key = lambda x: x[1])
left_next_index = list(range(-1, n - 1)) + [-1, -1]
right_next_index = list(range(1, n + 1)) + [n, n]
 
ans = 0
for i, p in sorted_lst:
    l2 = left_next_index[i]
    l1 = left_next_index[l2]
    r1 = right_next_index[i]
    r2 = right_next_index[r1]
    
    a = p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
    ans += a
    
    left_next_index[r1] = l2
    right_next_index[l2] = r1
print(ans)

Solution (Python):
N = int(input())
*p, = 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):
class SearchableBIT():
    def __init__(self,size):
        self.size=size
        self.data=[0]*(size+1)
        self.cnt=0
    def add(self,a):
        x=a
        self.cnt+=1
        while x<=self.size:
            self.data[x]+=1
            x+=x&-x
    def delete(self,x):
        self.cnt-=1
        while x<=self.size:
            self.data[x]-=1
            x+=x&-x
    def count(self,x):
        ret=0
        while x>0:
            ret+=self.data[x]
            x-=x&-x
        return ret
    def get_lower_i(self,i):
        ng=-1
        ok=self.size+1
        while ok-ng>1:
            mid=(ok+ng)//2
            if self.count(mid)>=i:
                ok=mid
            else:
                ng=mid
        return ok

n=int(input())
P=list(map(int,input().split()))
Idx=[0]*(n+1)
for i,p in enumerate(P):
    Idx[p]=i+1
BIT=SearchableBIT(n)
ans=0
for i in reversed(range(1,n+1)):
    idx=Idx[i]
    BIT.add(idx)
    cnt=BIT.count(idx)
    l_idx1=BIT.get_lower_i(cnt-1)
    l_idx2=BIT.get_lower_i(cnt-2)
    r_idx1=BIT.get_lower_i(cnt+1)
    r_idx2=BIT.get_lower_i(cnt+2)
    l1=idx-l_idx1
    l2=l_idx1-l_idx2
    r1=r_idx1-idx
    r2=r_idx2-r_idx1
    if r_idx1!=n+1:
        ans+=i*l1*r2
    if l_idx1!=0:
        ans+=i*l2*r1
print(ans)

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
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 RBNode:
    def __init__(self, val, is_red, parent=None, left=None, right=None):
        self.val = val
        self.parent = parent
        self.left = left
        self.right = right
        self.color = is_red


class RBTree:
    def __init__(self):
        self.root = None

    def left_rotate(self, node):
        
        right_node = node.right
        if right_node is None:
            return
        else:
            
            node.right = right_node.left
            if right_node.left is not None:
                right_node.left.parent = node
            right_node.parent = node.parent
            
            if node.parent is None:
                self.root = right_node
            elif node is node.parent.left:
                node.parent.left = right_node
            else:
                node.parent.right = right_node
            right_node.left = node
            node.parent = right_node

    def right_rotate(self, node):
        
        left_node = node.left
        if left_node is None:
            return
        else:
            
            node.left = left_node.right
            if left_node.right is not None:
                left_node.right.parent = node
            left_node.parent = node.parent
            
            if node.parent is None:
                self.root = left_node
            elif node is node.parent.left:
                node.parent.left = left_node
            else:
                node.parent.right = left_node
            left_node.right = node
            node.parent = left_node

    def insert(self, node):
        
        root = self.root
        insert_node_parent = None
        
        while root is not None:
            insert_node_parent = root
            if insert_node_parent.val < node.val:
                root = root.right
            else:
                root = root.left
        
        node.parent = insert_node_parent
        if insert_node_parent is None:
            
            self.root = node
        elif insert_node_parent.val > node.val:
            
            insert_node_parent.left = node
        else:
            insert_node_parent.right = node
        node.left = None
        node.right = None
        node.color = 1
        
        self.fix_insert(node)

    def fix_insert(self, node):
        
        if node.parent is None:
            node.color = 0
            self.root = node
            return
            
        
        while node.parent and node.parent.color == 1:
            if node.parent is node.parent.parent.left:
                uncle_node = node.parent.parent.right
                if uncle_node and uncle_node.color == 1:
                    
                    
                    
                    node.parent.color = 0
                    node.parent.parent.right.color = 0
                    node.parent.parent.color = 1
                    node = node.parent.parent
                    continue
                elif node is node.parent.right:
                    
                    
                    
                    node = node.parent
                    self.left_rotate(node)
                
                
                node.parent.color = 0
                node.parent.parent.color = 1
                self.right_rotate(node.parent.parent)
            else:
                uncle_node = node.parent.parent.left
                if uncle_node and uncle_node.color == 1:
                    
                    
                    
                    node.parent.color = 0
                    node.parent.parent.left.color = 0
                    node.parent.parent.color = 1
                    node = node.parent.parent
                    continue
                elif node is node.parent.left:
                    
                    
                    
                    node = node.parent
                    self.right_rotate(node)
                
                
                node.parent.color = 0
                node.parent.parent.color = 1
                self.left_rotate(node.parent.parent)
        self.root.color = 0

    def transplant(self, node_u, node_v):
        """
        replace u with v
        :param node_u: replaced node
        :param node_v:
        :return: None
        """
        if node_u.parent is None:
            self.root = node_v
        elif node_u is node_u.parent.left:
            node_u.parent.left = node_v
        elif node_u is node_u.parent.right:
            node_u.parent.right = node_v
        
        if node_v:
            node_v.parent = node_u.parent

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

    def maximum(self, node):
        """
        find the max node when node regard as a root node
        :param node:
        :return: max node
        """
        temp_node = node
        while temp_node.right:
            temp_node = temp_node.right
        return temp_node

    def minimum(self, node):
        """
        find the minimum node when node regard as a root node
        :param node:
        :return: minimum node
        """
        temp_node = node
        while temp_node.left:
            temp_node = temp_node.left
        return temp_node

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

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

    def delete(self, node):
        
        node_color = node.color
        if node.left is None:
            temp_node = node.right
            self.transplant(node, node.right)
        elif node.right is None:
            temp_node = node.left
            self.transplant(node, node.left)
        else:
            
            node_min = self.minimum(node.right)
            node_color = node_min.color
            temp_node = node_min.right
            
            if node_min.parent != node:
                self.transplant(node_min, node_min.right)
                node_min.right = node.right
                node_min.right.parent = node_min
            self.transplant(node, node_min)
            node_min.left = node.left
            node_min.left.parent = node_min
            node_min.color = node.color
        
        if node_color == 0:
            self.delete_fixup(temp_node)

    def delete_fixup(self, node):
        
        while node != self.root and node.color == 0:
            
            if node == node.parent.left:
                
                node_brother = node.parent.right

                
                
                if node_brother.color == 1:
                    node_brother.color = 0
                    node.parent.color = 1
                    self.left_rotate(node.parent)
                    node_brother = node.parent.right

                
                if (node_brother.left is None or node_brother.left.color == 0) and (
                        node_brother.right is None or node_brother.right.color == 0):
                    node_brother.color = 1
                    node = node.parent
                else:

                    
                    if node_brother.right is None or node_brother.right.color == 0:
                        node_brother.color = 1
                        node_brother.left.color = 0
                        self.right_rotate(node_brother)
                        node_brother = node.parent.right

                    
                    node_brother.color = node.parent.color
                    node.parent.color = 0
                    node_brother.right.color = 0
                    self.left_rotate(node.parent)
                node = self.root
                break
            else:
                node_brother = node.parent.left
                if node_brother.color == 1:
                    node_brother.color = 0
                    node.parent.color = 1
                    self.left_rotate(node.parent)
                    node_brother = node.parent.right
                if (node_brother.left is None or node_brother.left.color == 0) and (
                        node_brother.right is None or node_brother.right.color == 0):
                    node_brother.color = 1
                    node = node.parent
                else:
                    if node_brother.left is None or node_brother.left.color == 0:
                        node_brother.color = 1
                        node_brother.right.color = 0
                        self.left_rotate(node_brother)
                        node_brother = node.parent.left
                    node_brother.color = node.parent.color
                    node.parent.color = 0
                    node_brother.left.color = 0
                    self.right_rotate(node.parent)
                node = self.root
                break
        node.color = 0

    def inorder(self):
        res = []
        if not self.root:
            return res
        stack = []
        root = self.root
        stack.append(root)
        while stack:
            root = stack.pop()
            if root.parent:
                res.append({'parent': root.parent.val, 'val': root.val, 'color': root.color})
            else:
                res.append({'val': root.val, 'color': root.color})
            if root.left is not None:
                stack.append(root.left)
            if root.right is not None:
                stack.append(root.right)
        
        
        
        
        
        
        
        return res



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 = RBTree()
    for num, i in enumerate(L):
        rb.insert(RBNode(i, 1))
        l1 = rb.search_lower(i, -1)
        l2 = rb.search_lower(l1, -1)
        r1 = rb.search_higher(i, N)
        r2 = rb.search_higher(r1, N)
        
        ans += (abs(i - l1) * abs(r2 - r1) + abs(l1 - l2) * abs(r1 - i)) * (N - num)
    print(ans)
    
    return



if __name__ == '__main__':
    main()

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

    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 bisect_plus(self, i, t):
        L = i
        R = self.size
        R_prev = R
        sum_i = self.sum(i)
        while True:
            range_sum = self.sum(R) - sum_i
            if range_sum < t:
                if R == self.size:
                    return self.size + 1
                L, R = R, R_prev
            else:
                R_prev = R
                R = (L + R + 1) // 2
                if R == R_prev:
                    return R

    
    def bisect_minus(self, i, t):
        L = 1
        R = i
        L_prev = L
        sum_i = self.sum(i - 1)
        while True:
            range_sum = sum_i - self.sum(L - 1)
            if range_sum < t:
                if L == 1:
                    return 0
                L, R = L_prev, L
            else:
                L_prev = L
                L = (L + R) // 2
                if L == L_prev:
                    return L


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

place = [-1] * (N + 1)
for i in range(N):
    p = P[i]
    place[p] = i

ans = 0
big_place = Bit(N)
big_place.add(place[N] + 1, 1)
for i in range(N - 1, 0, -1):
    pos = place[i] + 1
    right = big_place.bisect_plus(pos, 1)
    right2 = big_place.bisect_plus(pos, 2)
    left = big_place.bisect_minus(pos, 1)
    left2 = big_place.bisect_minus(pos, 2)
    if left > 0:
        left_cand = left - left2
    else:
        left_cand = 0
    right_cand = right - pos
    ans += i * left_cand * right_cand

    if right < N + 1:
        right_cand = right2 - right
    else:
        right_cand = 0
    left_cand = pos - left
    ans += i * left_cand * right_cand

    big_place.add(pos, 1)

print(ans)

Solution (Python):
from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n = int(input())
p = list(rrd())

bit = [0] * 100005


def add(x):
    while x <= n:
        bit[x] += 1
        x += x & -x


def sum(x):
    tot = 0

    while x:
        tot += bit[x]
        x -= x & -x
    return tot


def search(x):
    tot = 0
    if x < 0:
        return tot
    for i in range(20)[::-1]:
        if (1 << i) + tot <= n and bit[(1 << i) + tot] <= x:
            tot += 1 << i
            x -= bit[tot]
    return tot + 1


idx = [0] * 100005

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

ans = 0
for i in range(n, 0, -1):

    j = sum(idx[i])
    l1 = search(j - 1)
    l2 = search(j - 2)
    r1 = search(j)
    r2 = search(j + 1)

    tt = (idx[i] - l1) * (r2 - r1) + (r1 - idx[i]) * (l1 - l2)
    ans += tt * i
    add(idx[i])

print(ans)

Solution (Python):
def binary_search(cond, left_initial, right_initial):

    left = left_initial
    right = right_initial

    while left + 1 < right:
        mid = (left + right) // 2

        if cond(mid):
            right = mid
        else:
            left = mid

    return left


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

    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 solve_e(n, p_list):
    ind_list = [0] * (n + 1)
    for i in range(n):
        ind_list[p_list[i]] = i + 1

    bit = Bit(n + 1)

    res = 0

    for i in range(n, 0, -1):
        ind = ind_list[i]
        bit.add(ind, 1)
        
        r1 = n + 1
        r2 = n + 1
        if bit.sum(n + 1) - bit.sum(ind) > 0:
            r1 = binary_search(lambda k: bit.sum(k) - bit.sum(ind) >= 1, ind, n + 1) + 1
        if bit.sum(n + 1) - bit.sum(ind) > 1:
            r2 = binary_search(lambda k: bit.sum(k) - bit.sum(ind) >= 2, ind, n + 1) + 1

        
        l1 = 0
        l2 = 0
        if bit.sum(ind) >= 2:
            l1 = binary_search(lambda k: bit.sum(ind) - bit.sum(k) <= 1, 0, ind) + 1
        if bit.sum(ind) >= 3:
            l2 = binary_search(lambda k: bit.sum(ind) - bit.sum(k) <= 2, 0, ind) + 1
        
        cnt = (ind - l1) * (r2 - r1) + (l1 - l2) * (r1 - ind)
        res += cnt * i

    return res


def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    print(solve_e(n, p_list))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



class BIT:
    '''
    a[1]~a[n]の数列を想定
    '''

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def add(self, index, x):
        '''
        a[index]にxを加算
        '''
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self, index):
        '''
        a[1]~a[index]の和
        '''
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self, value):
        '''
        sum(index)>=value を満たす最小のindex
        sum(n)<value のとき n+1 を返す
        '''
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step //= 2
        return i + 1
        
        
def index_sort(A,reverse=False):
    x = []
    for i,a in enumerate(A):
        x.append((a,i))
    if reverse:
        return sorted(x, key=lambda x: -x[0])
    else:
        return sorted(x, key=lambda x: x[0])

      
N = I()
P = III()

bit = BIT(N)
x = index_sort(P,True)

ans = 0
for i in range(N):
    index = x[i][1]
    if index>=1:
        L = bit.sum(index)
    else:
        L = 0
    wi = bit.search(L-1) if L>=2 else 0
    xi = bit.search(L) if L>=1 else 0

    R = bit.sum(N)-bit.sum(index+1)
    yi = bit.search(L+1)
    zi = bit.search(L+2)

    ci = (xi-wi)*(yi-index-1) + (index+1-xi)*(zi-yi)
    ans += ci*x[i][0]
    bit.add(index+1, 1)

print(ans)

Solution (Python):
N = int(input())
P = list(map(int, input().split()))
 
left_bigger  = [0] + [i for i in range(N+1)]
right_bigger = [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:
    l0=left_bigger[i]
    l1=left_bigger[l0]
    r0=right_bigger[i]
    r1=right_bigger[r0]
    
    ans += ((r1-r0)*(i-l0) + (r0-i)*(l0-l1))*v
    left_bigger[r0]=l0
    right_bigger[l0]=r0
print(ans)

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

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
L = [i for i in range(-1, N-1)]
R = [i for i in range(1, N+1)]

for p in range(1,N+1):
    i = I[p-1]

    if R[i] < N:
        L[R[i]] = L[i]
    if L[i] >= 0:
        R[L[i]] = R[i]

    l1 = L[i]
    l2 = L[l1] if l1 >= 0 else -1
    r1 = R[i]
    r2 = R[r1] if r1 < N else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))

print(ans)