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

''' 
    [Bit]
'''
class Bit:
    """ used for only int(>=0) 
        1-indexed (ignore 0-index)
    """
    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):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        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_

    def get_less_than_x_cnt(self, x):
        """ 累積和がx未満 の個数 """
        lb_pos, lb_sum = self.lower_bound(x)
        return lb_pos-1

    def get_less_than_and_x_cnt(self, x):
        """ 累積和がx以下 の個数 """
        lb_pos, lb_sum = self.lower_bound(x+1)
        return lb_pos-1
    
    def get_more_than_x_cnt(self, x):
        """ 累積和がxより大きい 個数 """
        return self.size - self.get_less_than_and_x_cnt(x)


n = int(input())
pl = list(map(int, input().split()))
pll = []
for i,p in enumerate(pl):
    pll.append((p,i+1))

pll.sort(reverse=True)
bit = Bit(n)
ans = 0
for p,i in pll:
    ix = bit.sum(i)
    
    if ix == 0:
        lmax = 0
        lmin = 0
        lcnt = 0
    else:
        lmax, _ = bit.lower_bound(ix)
        if ix == 1:
            lmin = 0
        else:
            lmin, _ = bit.lower_bound(ix-1)
        lcnt = lmax - lmin
    
    rmin, _ = bit.lower_bound(ix+1)
    rmax, _ = bit.lower_bound(ix+2)
    rcnt = rmax - rmin

    comb = lcnt*(rmin-i) + (i-lmax)*rcnt
    ans += comb*p

    bit.add(i,1)
    
    
    

print(ans)

Solution (Python):

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

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

    l_idx = list(range(-1, N - 1)) + [-1, -1]
    r_idx = list(range(1, N + 1)) + [N, N]  

    ans = 0
    for p in range(1, N + 1):
        x = P[p]

        l1 = l_idx[x]
        l2 = l_idx[l1]
        r1 = r_idx[x]
        r2 = r_idx[r1]

        cmb = (x - l1) * (r2 - r1) + (l1 - l2) * (r1 - x)
        ans += p * cmb

        l_idx[r1] = l1
        r_idx[l1] = r1

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):

from bisect import bisect_left, bisect_right
class OrderedSet:
    def __init__(self, a):
        self.c = {}
        self.a_sort = sorted(list(set(a)))
        for i, a in enumerate(self.a_sort):
            self.c[a] = i + 1
        self.r = {v: k for k, v in self.c.items()}
        self.size = len(self.c)
        self.tree = [0] * (self.size + 1)
        self.num = [0] * self.size
        self.all_count = 0  

    
    def _sum(self, index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    
    def insert(self, x, k=1):
        index = self.c[x]
        self.num[index - 1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k

    
    def erase(self, x, k=1):
        self.insert(x, k=-k)

    
    def count(self, x):
        return self.num[self.c[x] - 1]

    
    def get_kth_bottom(self, k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i + 1]

    
    def get_kth_top(self, k):
        return self.get_kth_bottom(self.all_count - k + 1)

    
    def lower_bound(self, x):
        p = bisect_left(self.a_sort, x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)

    
    def upper_bound(self, x):
        p = bisect_right(self.a_sort, x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)


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

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

    OS = OrderedSet(P)
    ans = 0
    for i in range(N, 0, -1):
        p = P[i]
        c = OS.lower_bound(p)
        d = None if c is None else OS.lower_bound(c + 1)
        b = OS.upper_bound(p)
        a = None if b is None else OS.upper_bound(b - 1)

        a = a if a is not None else 0
        d = d if d is not None else N + 1

        if b is None:
            if c is not None:
                ans += i * p * (d - c)
        elif c is None:
            ans += i * (b - a) * (N - p + 1)
        else:
            ans += i * ((b - a) * (c - p) + (p - b) * (d - c))

        OS.insert(p)

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
PiがX_LRに選ばれる時の通り数を考える
左右それぞれに，自分より大きいものが出てくる場所を近い順に2箇所上げておけば良い．

これを計算するにはPの大きい順に見ていき，L=[]にインデックスを追加していく．bisectで新しく見たやつのindexの挿入かっしょを調べて左右を見る
=>要素の追加がうまくできない，seg木 or マルチセット
"""

def main():

    
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        
        

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            
            
            
            
            

            self.cnt=0
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  
            
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                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(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1

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

            self.cnt-=1

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

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

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

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


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

        def len(self):
            return self.cnt

    


    import bisect
    
    mod=10**9+7
    N=I()
    P=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        P[i]=[P[i],i]
        
    P.sort(reverse=True)
    
    ssl = SquareSkipList(square=2000)
    ssl.add(-2)
    ssl.add(-1)
    ssl.add(N)
    ssl.add(N+1)
    
    ans=0
    for i in range(N):
        p=P[i][0]
        index=P[i][1]
        l1=ssl.search_lower(index)
        l2=ssl.search_lower(l1)
        r1=ssl.search_higher(index)
        r2=ssl.search_higher(r1)
        
        
        if l2==-2:
            l2=-1
        if r2==N+1:
            r2=N
        
        a=l1-l2
        b=index-l1
        c=r1-index
        d=r2-r1
        
        ssl.add(index)
        
        temp=a*c + b*d
        ans+=temp*p
        
    print(ans)
        
        
        
            
    
    

main()

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
P = list(map(int,input().split()))

A = [[P[i], i] for i in range(len(P))]
A.sort(reverse=True)


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

B = Bit(n+1)
L0 = [[0] * 2 for i in range(n)]
for i in range(n):
    ind = A[i][1]
    B.add(ind+1, 1)
    s = B.sum(ind+1)
    R = [-1, -1]
    for j in range(2):
        l = -1
        r = ind+1
        m = (l+r+1)//2
        while r-l > 1:
            if B.sum(m) < s-1-j:
                l = m
            else:
                r = m
            m = (l+r+1)//2
        R[j] = r
    L0[i] = [ind+1-R[0], R[0]-R[1]]
    


    
B = Bit(n+1)
L1 = [[0] * 2 for i in range(n)]
for i in range(n):
    ind = n-1-A[i][1]
    B.add(ind+1, 1)
    s = B.sum(ind+1)
    R = [-1, -1]
    for j in range(2):
        l = -1
        r = ind+1
        m = (l+r+1)//2
        while r-l > 1:
            if B.sum(m) < s-1-j:
                l = m
            else:
                r = m
            m = (l+r+1)//2
        R[j] = r
    L1[i] = [ind+1-R[0], R[0]-R[1]]
    


ans = 0
for i in range(n):
    ans += (n-i) * (L0[i][0] * L1[i][1] + L0[i][1] * L1[i][0])
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
A = IL()

P = [None for i in range(N)]
for i in range(N):
  P[A[i]-1] = i

R = DD(lambda:N)
L = DD(lambda:-1)
R2 = DD(lambda:N)
L2 = DD(lambda:-1)

stack = []
stack2 = []
for i in range(N):
  while stack2 and stack2[-1]<A[i]:
    R2[stack2.pop()-1] = i
  temp = []
  while stack and stack[-1]<A[i]:
    a = stack.pop()
    R[a-1] = i
    temp.append(a)
  while temp:
    stack2.append(temp.pop())
  stack.append(A[i])
  
stack = []
stack2 = []
for i in range(N)[::-1]:
  while stack2 and stack2[-1]<A[i]:
    L2[stack2.pop()-1] = i
  temp = []
  while stack and stack[-1]<A[i]:
    a = stack.pop()
    L[a-1] = i
    temp.append(a)
  while temp:
    stack2.append(temp.pop())
  stack.append(A[i])

ans = 0
for i in range(N):
  a,b,c,d,e = L2[i],L[i],P[i],R[i],R2[i]
  ans += ((c-b)*(e-d) + (b-a)*(d-c))*(i+1)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

class Node: 
    def __init__(self, height, key, x):
        self.height = height 
        self.key    = key    
        self.value  = x      
        self.lst    = None   
        self.rst    = None   

def height(t): return 0 if t is None else t.height

def bias(t): return height(t.lst) - height(t.rst)

def modHeight(t): t.height = 1 + max(height(t.lst), height(t.rst))

def rotateL(v):
    u = v.rst; t2 = u.lst
    u.lst = v; v.rst = t2
    modHeight(u.lst)
    modHeight(u)
    return u

def rotateR(u):
    v = u.lst; t2 = v.rst
    v.rst = u; u.lst = t2
    modHeight(v.rst)
    modHeight(v)
    return v

def rotateLR(t):
    t.lst = rotateL(t.lst)
    return rotateR(t)

def rotateRL(t):
    t.rst = rotateR(t.rst)
    return rotateL(t)

def keys_sub(t):
    if t is None: return []
    return keys_sub(t.lst) + [t.key] + keys_sub(t.rst)

def values_sub(t):
    if t is None: return []
    return values_sub(t.lst) + [t.value] + values_sub(t.rst)

def items_sub(t):
    if t is None: return []
    return items_sub(t.lst) + [(t.key, t.value)] + items_sub(t.rst)



class AVLMap:
    def __init__(self):
        self.root   = None  
        self.change = False 
        self.lmax   = None  
        self.value  = None  
    
    def balanceLi(self, t): return self.balanceL(t)
    def balanceRi(self, t): return self.balanceR(t)

    def balanceLd(self, t): return self.balanceR(t)
    def balanceRd(self, t): return self.balanceL(t)

    def balanceL(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == 2:
            if bias(t.lst) >= 0:
                t = rotateR(t)
            else:
                t = rotateLR(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

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

     

    def insert(self, key, x): self.root = self.insert_sub(self.root, key, x)

    def insert_sub(self, t, key, x):
        if t is None:
            self.change = True
            return Node(1, key, x)
        elif key < t.key:
            t.lst = self.insert_sub(t.lst, key, x)
            return self.balanceLi(t)
        elif key > t.key:
            t.rst = self.insert_sub(t.rst, key, x)
            return self.balanceRi(t)
        else:
            self.change = False
            t.value = x
            return t

    
    def set_append(self, key, x):
        if self.member(key):
            pass
        else:
            self.insert(key, x)
    
    def list_append(self, key, x):
        self.insert(key, x)
        
    

    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        elif key < t.key:
            t.lst = self.delete_sub(t.lst, key)
            return self.balanceLd(t)
        elif key > t.key:
            t.rst = self.delete_sub(t.rst, key)
            return self.balanceRd(t)
        else:
            if t.lst is None:
                self.change = True
                return t.rst 
            else:
                t.lst = self.delete_max(t.lst) 
                t.key = self.lmax 
                t.value = self.value
                return self.balanceLd(t)

    def delete_max(self, t):
        if t.rst is not None:
            t.rst = self.delete_max(t.rst)
            return self.balanceRd(t)
        else:
            self.change = True
            self.lmax = t.key 
            self.value = t.value
            return t.lst 

    
    def member(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return True
        return False

    
    def lookup(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return t.value
        return None       

    
    def upper_bound(self, x):
        t = self.root
        res = 0
        ans = None
        while t is not None:
            if x < t.key:
                ans = t.key
                t = t.lst
            elif x > t.key:
                t = t.rst
            else:
                return t.key
        return ans
    
    
    def lower_bound(self, x):
        t = self.root
        res = 0
        ans = None
        while t is not None:
            if x < t.key:
                t = t.lst
            elif x > t.key:
                ans = t.key
                t = t.rst
            else:
                return int(t.key)
        return ans
            

    def isEmpty(self): return self.root is None

    def clear(self): self.root = None

    def keys(self): return keys_sub(self.root)

    def values(self): return values_sub(self.root)

    def items(self): return items_sub(self.root)

    def size(self): return len(self.keys())




def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    index = [0]*n
    for i in range(n):
        index[a[i]-1] = i
    
    avl = AVLMap()
    
    ans = 0
    avl.insert(index[n-1], n-1)
    for i in range(n-2, -1, -1):
        ind = index[i]
        
        p, q, r, s = 0, 0, 0, 0
        key_upper = avl.upper_bound(ind)
        if key_upper != None:
            p = key_upper
            key_upper = avl.upper_bound(key_upper+1)
            if key_upper == None:
                q = n
            else:
                q = key_upper
        else:
            p = n
            q = n
        
        
        
        
        
        key_lower = avl.lower_bound(ind)
        if key_lower != None:
            r = key_lower
            key_lower = avl.lower_bound(key_lower-1)
            if key_lower == None:
                s = -1
            else:
                s = key_lower
        else:
            r = -1
            s = -1
        

        ans += (i+1)*((p-ind)*(r-s)+(ind-r)*(q-p))
        
        
        avl.insert(ind, i)
    
    print(ans)
    
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
from bisect import*
class SqrtSet:
    def __init__(self,block_limit=201):
        self.key=[]
        self.child=[[]]
        self.block_limit=block_limit
    def le(self,key):
        ret=key
        i=bisect_left(self.key,key)
        if i:ret=self.key[i-1]
        block=self.child[i]
        i=bisect_left(block,key)
        if i:ret=block[i-1]
        return ret
    def ge(self,key):
        ret=key
        i=bisect(self.key,key)
        if i<len(self.key):ret=self.key[i]
        block=self.child[i]
        i=bisect(block,key)
        if i<len(block):ret=block[i]
        return ret
    def insert(self,key):
        i=bisect(self.key,key)
        block=self.child[i]
        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 main():
    n,*p=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(p,1):l[v-1]=i
    t=SqrtSet()
    insert,le,ge=t.insert,t.le,t.ge
    insert(0),insert(n+1)
    a=0
    for i,v in list(enumerate(l,1))[::-1]:
        f,b=ge(v),le(v)
        g,c=ge(f),le(b)
        a+=i*((f-v)*(b-c)+(v-b)*(g-f))
        insert(v)
    print(a)
main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
p = list(map(lambda x: int(x)-1, input().split()))

def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)

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


def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

def index(bit, v):
    """a1,...,aiの和がv以上になる最小のindexを求める
    存在しないとき配列サイズを返す
    """
    i = 0
    n = len(bit)-1
    k = 1<<((n-1).bit_length())



    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    if v==1:
        return i+1
    else:
        return n+1

ind = [None]*n
for i,num in enumerate(p):
    ind[num] = i
bit = [0]*(n+1)
l = [None]*n
l2 = [None]*n
r = [None]*n
r2 = [None]*n
for num in range(n-1, -1, -1):
    i = query(bit, ind[num])
    if i==0:
        l[ind[num]] = -1
        l2[ind[num]] = -1
    elif i==1:
        l[ind[num]] = index(bit, i) - 1
        l2[ind[num]] = -1
    else:
        l[ind[num]] = index(bit, i) - 1
        l2[ind[num]] = index(bit, i-1) - 1
    r[ind[num]] = index(bit, i+1) - 1
    r2[ind[num]] = index(bit, i+2) - 1
    add(bit, ind[num]+1, 1)

    
ans = 0
for i, (num, li, li2, ri, ri2) in enumerate(zip(p, l, l2, r, r2)):
    v = 0
    if li>=0:
        v += (ri-i)*(li-li2)
    if ri<n:
        v += (i-li)*(ri2-ri)

    ans += v * (num+1)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i






def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    
    i = 0
    s = 0
    step = 1<<(N.bit_length()-1)
    while step:
        if i+step <= N and s + tree[i+step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i+1
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) 
    BIT_add(c)
    R = N-x-L 
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        
        coef += (b-a) * (d-c)
    if d != 0:
        
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i






def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    
    
    
    
    
    
    
    
    
    
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) 
    BIT_add(c)
    R = N-x-L 
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        
        coef += (b-a) * (d-c)
    if d != 0:
        
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)