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 time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = TwoLayerSet(1/100)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Solution (Python):
def argsort(a):
    return list(map(lambda z: z[1], sorted(zip(a, range(len(a))))))

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

a = argsort(P)
left = [i for i in range(N)]
right = [i for i in range(N)]
result = 0
for i in range(1, N):
    k = a[i - 1]
    extend_left = k - 1 >= 0 and P[k - 1] < i
    extend_right = k + 1 < N and P[k + 1] < i
    if extend_left and extend_right:
        L = left[k - 1]
        R = right[k + 1]
    elif extend_left:
        L = left[k - 1]
        R = k
    elif extend_right:
        R = right[k + 1]
        L = k
    else:
        L = k
        R = k
    right[L] = R
    left[R] = L
    if L - 1 >= 0:
        if L - 2 >= 0 and P[L - 2] < i:
            LL = left[L - 2]
        else:
            LL = L - 1
        result += ((L - 1) - LL + 1) * (R - k + 1) * i;
    if R + 1 < N:
        if R + 2 < N and P[R + 2] < i:
            RR = right[R + 2]
        else:
            RR = R + 1
        result += (RR - (R + 1) + 1) * (k - L + 1) * i;
print(result)

Solution (Python):
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)

Solution (Python):
class Avltree:

  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())
p=list(map(int,input().split()))
ans=0
l=[0]*n
for i in range(n):
  l[p[i]-1]=i
root=Avltree()
for i in range(n-1,-1,-1):
  root.insert(l[i])
  ans+=(i+1)*(root.search_lower(l[i],-1)-root.search_lower((root.search_lower(l[i],-1)),-1))*(root.search_higher(l[i],n)-l[i])
  ans+=(i+1)*(l[i]-root.search_lower(l[i],-1))*(root.search_higher(root.search_higher(l[i],n),n)-root.search_higher(l[i],n))
print(ans)

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

PIdx = sorted([(i + 1, v) for i, v in enumerate(P)], key = lambda x: x[1])

L = [0]
for i in range(N + 1):
    L.append(i)

R = [i + 1 for i in range(N + 1)]
R.append(N + 1)

ans = 0
for i, v in PIdx:
    l1 = L[i]
    l2 = L[l1]
    r1 = R[i]
    r2 = R[r1]

    ans += v * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))

    L[r1] = l1
    R[l1] = r1

print(ans)

Solution (Python):
class BIT:
  def __init__(self, n):
    self.N = n
    self.tree = [0]*(n+1)
  
  def BIT_add(self, i):
    while i <= self.N:
      self.tree[i] += 1
      i += i&(-i)
  
  def BIT_sum(self, i):
    s = 0
    while i:
      s += self.tree[i]
      i -= i&(-i)
    return s
  
  def BIT_search(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())
bit = BIT(N)
p = [None]+[int(c) for c in input().split()]
p_to_i = [None]*(N+1)
for i, x in enumerate(p[1:], 1):
  p_to_i[x] = i
  
ans = 0
for x in range(N,0,-1):
  c = p_to_i[x]
  L = bit.BIT_sum(c)
  bit.BIT_add(c)
  R = N-x-L
  a = bit.BIT_search(L-1) if L>=2 else 0
  b = bit.BIT_search(L) if L >= 1 else 0
  d = bit.BIT_search(L+2) if R >= 1 else N+1
  e = bit.BIT_search(L+3) if R >= 1 else N+1
  
  coef = 0
  if b != 0:
    coef += (b-a) * (d-c)
  if d != 0:
    coef += (e-d) * (c-b)
  
  ans += x*coef
print(ans)

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_left(self, l, r, x):
        """ 区間[l,r]で左からx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return -1

    def bisearch_right(self, l, r, x):
        """ 区間[l,r]で右からx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -1

N = INT()
A = LIST()

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

bit = BIT(N)
ans = [0] * (N+1)

for a in range(N, 0, -1):
    
    idx = idxs[a]
    
    res = bit.bisearch_right(0, idx, 2)
    p = res + 1 if res != -1 else 0
    
    res = bit.bisearch_right(0, idx, 1)
    q = res + 1 if res != -1 else 0
    
    res = bit.bisearch_left(idx, N-1, 1)
    r = res - 1 if res != -1 else N - 1
    
    res = bit.bisearch_left(idx, N-1, 2)
    s = res - 1 if res != -1 else N - 1
    
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    
    bit.add(idx, 1)

print(sum(ans))

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_left(self, l, r, x):
        """ 区間[l,r]で左からx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return -1

    def bisearch_right(self, l, r, x):
        """ 区間[l,r]で右からx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -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]
    
    p = bit.bisearch_right(0, idx, 2) + 1
    
    q = bit.bisearch_right(0, idx, 1) + 1
    
    r = bit.bisearch_left(idx, N+1, 1) - 1
    
    s = bit.bisearch_left(idx, N+1, 2) - 1
    
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    
    bit.add(idx, 1)

print(sum(ans))

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_left(self, l, r, x):
        """ 区間[l,r]で左からx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return -1

    def bisearch_right(self, l, r, x):
        """ 区間[l,r]で右からx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -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]
    
    p = bit.bisearch_right(0, idx, 2) + 1
    
    q = bit.bisearch_right(0, idx, 1) + 1
    
    r = bit.bisearch_left(idx, N+1, 1) - 1
    
    s = bit.bisearch_left(idx, N+1, 2) - 1
    
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    
    bit.add(idx, 1)

print(sum(ans))

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_left(self, l, r, x):
        """ 区間l,rで左からx番目の値がある位置 """
        l_val = self.sum(l)
        ok = r
        ng = l
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_val >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def bisearch_right(self, l, r, x):
        """ 区間l,rで右からx番目の値がある位置 """
        r_val = self.sum(r)
        ok = r
        ng = l
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if r_val - self.sum(mid) < x:
                ok = mid
            else:
                ng = mid
        return ok

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]
    
    p = bit.bisearch_right(-1, idx, 2) + 1
    
    q = bit.bisearch_right(-1, idx, 1) + 1
    
    r = bit.bisearch_left(idx, N+1, 1) - 1
    
    s = bit.bisearch_left(idx, N+1, 2) - 1
    
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    
    bit.add(idx, 1)

print(sum(ans))

Solution (Python):
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

    def add(self, idx, x):
        
        
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        
        
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        
        
        if w <= 0:
            return 0
        idx = 0  
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

    def bisect_right(self, w):
        
        
        if w < 0:
            return 0
        idx = 0  
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


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

p2idx = [0] * (n + 1)
for i in range(1, n + 1):
    p2idx[p[i - 1]] = i

ans = 0
bit = BIT1(n)
for x in reversed(range(1, n + 1)):
    idx = p2idx[x]
    bit.add(idx, 1)
    idx_rank = bit.sum(idx)
    idx_l2 = bit.bisect_left(idx_rank - 2)
    idx_l1 = bit.bisect_left(idx_rank - 1)
    idx_r1 = bit.bisect_left(idx_rank + 1)
    idx_r2 = bit.bisect_left(idx_rank + 2)

    cnt = 0
    cnt += (idx_l1 - idx_l2) * (idx_r1 - idx)
    cnt += (idx - idx_l1) * (idx_r2 - idx_r1)
    ans += x * cnt
    

print(ans)

Solution (Python):
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

    def add(self, idx, x):
        
        
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        
        
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        
        
        if w <= 0:
            return 0
        idx = 0  
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

    def bisect_right(self, w):
        
        
        if w < 0:
            return 0
        idx = 0  
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


n = int(input())
p = [0] + list(map(int, input().split()))

p2idx = [0] * (n + 1)
for i in range(1, n + 1):
    p2idx[p[i]] = i

ans = 0
bit = BIT1(n)
for x in reversed(range(1, n + 1)):
    idx = p2idx[x]
    bit.add(idx, 1)
    idx_rank = bit.sum(idx)
    idx_l2 = bit.bisect_left(idx_rank - 2)
    idx_l1 = bit.bisect_left(idx_rank - 1)
    idx_r1 = bit.bisect_left(idx_rank + 1)
    idx_r2 = bit.bisect_left(idx_rank + 2)

    cnt = 0
    cnt += (idx_l1 - idx_l2) * (idx_r1 - idx)
    cnt += (idx - idx_l1) * (idx_r2 - idx_r1)
    ans += x * cnt
    

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A 
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

    def range_sum(self,l,r):
        assert(self.__inv)
        return self.__inv(self.sum(r),self.sum(l))

    def bisect_left(self,w,increase=True):
        n=self.__n
        k=2**((self.__n-1).bit_length())
        res=0
        now=self.__e
        while(k):
            if(res+k<=n and self.__dot(now,self.__node[res+k])<w and increase):
                now=self.__dot(now,self.__node[res+k])
                res+=k
            elif(res+k<=n and self.__dot(now,self.__node[res+k])>w and (not increase)):
                now=self.__dot(now,self.__node[res+k])
                res+=k
            k//=2
        return res

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    idx=[0]*n
    for i,a in enumerate(A):
        idx[a-1]=i

    from operator import add
    bit=BIT([0]*n,add,0)

    ans=0
    for k in range(n,0,-1):
        i=idx[k-1]
        bit.add(i)
        s=bit.sum(i+1)
        l0=bit.bisect_left(s-1)-(s<=1)
        l1=bit.bisect_left(s-2)-(s<=2)
        r0=bit.bisect_left(s+1)
        r1=bit.bisect_left(s+2)
        ans+=k*((i-l0)*(r1-r0)+(l0-l1)*(r0-i))
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A 
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        i+=1
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

    def range_sum(self,l,r):
        assert(self.__inv)
        return self.__inv(self.sum(r-1),self.sum(l-1))

    def bisect_left(self,w,increase=True):
        n=self.__n
        k=2**((self.__n-1).bit_length())
        res=0
        now=self.__e
        while(k):
            if(res+k<=n and self.__dot(now,self.__node[res+k])<w and increase):
                now=self.__dot(now,self.__node[res+k])
                res+=k
            elif(res+k<=n and self.__dot(now,self.__node[res+k])>w and (not increase)):
                now=self.__dot(now,self.__node[res+k])
                res+=k
            k//=2
        return res

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    idx=[0]*n
    for i,a in enumerate(A):
        idx[a-1]=i

    from operator import add
    bit=BIT([0]*n,add,0)

    ans=0
    for k in range(n,0,-1):
        i=idx[k-1]
        bit.add(i)
        s=bit.sum(i)
        l0=bit.bisect_left(s-1)-(s<=1)
        l1=bit.bisect_left(s-2)-(s<=2)
        r0=bit.bisect_left(s+1)
        r1=bit.bisect_left(s+2)
        ans+=k*((i-l0)*(r1-r0)+(l0-l1)*(r0-i))
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A 
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        i+=1
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

    def range_sum(self,l,r):
        assert(self.__inv)
        return self.__inv(self.sum(r),self.sum(l))

    def bisect_left(self,w,increase=True):
        if(w>self.sum(self.__n-1)): return self.__n
        n=2**((self.__n-1).bit_length())
        res=0
        while(n>0):
            if(res+n<=self.__n and ((w>self.__node[res+n])^(not increase))):
                w-=self.__node[res+n]
                res+=n
            n//=2
        return res

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    idx=[0]*n
    for i,a in enumerate(A): idx[a-1]=i
    from operator import add
    bit=BIT([0]*n,add,0)

    
    ans=0
    for k in range(n,0,-1):
        i=idx[k-1]
        bit.add(i)
        s=bit.sum(i)
        l0=bit.bisect_left(s-1)-(s<=1)
        l1=bit.bisect_left(s-2)-(s<=2)
        r0=bit.bisect_left(s+1)
        r1=bit.bisect_left(s+2)
        ans+=k*((l0-l1)*(r0-i)+(r1-r0)*(i-l0))
    print(ans)
resolve()