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 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):
N = int(input())
P = list(map(int, input().split()))

class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + 1
    s.T[k - 1] = max(s.T[k - 1], v)
    k += k & -k
    while k <= s.N:
      s.T[k - 1] = max(s.T[k - 1], v)
      k += k & -k
  def getV(s, x):
    if x <= 0:
      return 0
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans = max(ans, s.T[x - 1])
      x -= x & -x
    return ans

class segMin:
  inf = N + 1
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    if l > r:
      return s.inf
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

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

TMa = BIT(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  
  t = D[i]
  ma = TMa.getV(t)
  ma2 = TMa.getV(ma)

  mi = TMi.getV(t, N + 1)
  mi2 = TMi.getV(mi + 1, N + 1)
  
  TMa.update(t, t)
  TMi.update(t, t)
  ans += (mi - t) * (ma - ma2) * i
  ans += (mi2 - mi) * (t - ma) * i

print(ans)

Solution (Python):

from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    
    
    
    
    
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        
        
        
        
        inf = float("inf")
        self.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)

    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]

    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):
        
        
        
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

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


def main():
    
    inf = float("inf")
    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])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

Solution (Python):
from operator import itemgetter


class RedBlackTree:
    
    
    
    
    
    
    

    def __init__(self, EOT=-1):
        self.EOT = EOT
        self.root = self._leaf()

    def _leaf(self):
        return [None, None, self.EOT, 0, 0]

    def _rotate(self, node, r):
        child = node[r ^ 1]
        node[r ^ 1] = child[r]
        child[r] = node
        child[3] = node[3]
        node[3] = 1
        child_count = child[4]
        child[4] = node[4]
        node[4] -= child_count - node[r ^ 1][4]
        return child

    def insert(self, x):
        stack = []
        node = self.root
        while node[2] != self.EOT:
            

            to_right = x >= node[2]
            stack.append((node, to_right))
            node = node[to_right]

        
        node[0] = self._leaf()
        node[1] = self._leaf()
        node[2] = x
        node[3] = 1
        node[4] = 1

        
        for parent, _ in stack:
            parent[4] += 1

        
        while stack:
            parent, r = stack.pop()
            if parent[3] == 1:
                node = parent
                continue
            parent[r] = node
            node, flag = self._balance_insert(parent, r)

            if stack and flag == True:
                parent, r = stack.pop()
                parent[r] = node
                break

        else:
            
            self.root = node
            self.root[3] = 0

    def _balance_insert(self, node, r):
        flag = True
        if node[r][r ^ 1][3] == 1:
            node[r] = self._rotate(node[r], r)
        if node[r][r][3] == 1:
            if node[r ^ 1][3] == 1:
                node[3] = 1
                node[r ^ 1][3] = node[r][3] = 0
                flag = False
            else:
                node = self._rotate(node, r ^ 1)
        return node, flag

    def delete(self, x):
        node = self.root
        stack = []
        while node[2] != x:
            r = node[2] < x
            stack.append((node, r))
            node = node[r]

        
        if node[2] == self.EOT:
            return

        
        if node[0][2] != self.EOT and node[1][2] != self.EOT:
            stack.append((node, 1))
            min_node = self.get_min(node[1], stack)
            node[2] = min_node[2]
            node = min_node

        
        for parent, _ in stack:
            parent[4] -= 1

        
        parent, r = stack[-1]
        if node[0][2] == self.EOT:
            parent[r] = node[1]
            node[1][3] = 0
            
            if node[1][2] != self.EOT or node[3] == 1:
                return
        elif node[1][2] == self.EOT:
            parent[r] = node[0]
            node[0][3] = 0
            return

        
        while stack:
            parent, r = stack.pop()
            node, flag = self._balance_delete(parent, r)

            if stack and flag == True:
                parent, r = stack.pop()
                parent[r] = node
                break
        else:
            
            self.root = node
            self.root[3] = 0

    def get_min(self, node, stack):
        while node[0][2] != self.EOT:
            stack.append((node, 0))
            node = node[0]
        return node

    def _balance_delete(self, node, r):
        if node[r ^ 1][r][3] == 0 and node[r ^ 1][r ^ 1][3] == 0:
            if node[r ^ 1][3] == 0:
                node[r ^ 1][3] = 1
                if node[3] == 0:
                    return node, False
                node[3] = 0
            else:
                node = self._rotate(node, r)
                node[r], _ = self._balance_delete(node[r], r)
        else:
            if node[r ^ 1][r][3] == 1:
                node[r ^ 1] = self._rotate(node[r ^ 1], r ^ 1)
            node = self._rotate(node, r)
            node[r][3] = 0
            node[r ^ 1][3] = 0
        return node, True

    def upper_bound(self, x):
        """
        :return Smallest y satisfying x < y and its leftmost index.
                If not exists, (EOT, length) will be returned.
        """
        node = self.root
        y = self.EOT
        i = node[4]
        j = 0
        while node[2] != self.EOT:
            if x < node[2]:
                y = node[2]
                i = j + node[0][4]
                node = node[0]
            else:
                j += node[0][4] + 1
                node = node[1]
        return y, i

    def lower_bound(self, x):
        """
        :return Smallest y satisfying x <= y and its leftmost index.
                If not exists, (EOT, length) will be returned.
        """
        node = self.root
        y = self.EOT
        i = node[4]
        j = 0
        while node[2] != self.EOT:
            if x <= node[2]:
                y = node[2]
                i = j + node[0][4]
                node = node[0]
            else:
                j += node[0][4] + 1
                node = node[1]
        return y, i

    def get_by_index(self, i):
        """
        :return (0-indexed) i-th smallest item.
                If i is greater than length, EOT will be returned.
        """
        node = self.root
        if node[4] <= i:
            return self.EOT
        j = i
        while node[2] != self.EOT:
            left_count = node[0][4]
            if left_count == j:
                return node[2]
            elif left_count > j:
                node = node[0]
            else:
                j -= left_count + 1
                node = node[1]

    def debug_print(self):
        self._debug_print(self.root, 0)

    def _debug_print(self, node, depth):
        if node[2] != self.EOT:
            self._debug_print(node[0], depth + 1)
            print('      ' * depth, 'BR'[node[3]], node[2], node[4])
            self._debug_print(node[1], depth + 1)


n = int(input())
ppp = list(map(int, input().split()))
pps = list(enumerate(ppp))
pps.sort(reverse=True, key=itemgetter(1))

rbt = RedBlackTree(-2)
rbt.insert(-1)
rbt.insert(-1)
rbt.insert(n)
rbt.insert(n)

ans = 0
for i, p in pps:
    r1, j = rbt.upper_bound(i)
    r2 = rbt.get_by_index(j + 1)
    l1 = rbt.get_by_index(j - 1)
    l2 = rbt.get_by_index(j - 2)
    ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
    rbt.insert(i)
print(ans)

Solution (Python):
from heapq import heappush, heappop

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

dpl = [[] for _ in range(N)]
dpr = [[] for _ in range(N)]
q = []
for i in range(N-1, -1, -1) :
    L = []
    while len(q) > 0 and q[0][0] < P[i] :
        v, j = heappop(q)
        if len(dpl[j]) == 0 :
            L.append([v, j])
        dpl[j].append(i)
    for v, j in L :
        heappush(q, [v, j])
    heappush(q, [P[i], i])

q = []
for i in range(N) :
    L = []
    while len(q) > 0 and q[0][0] < P[i] :
        v, j = heappop(q)
        if len(dpr[j]) == 0 :
            L.append([v, j])
        dpr[j].append(i)
    for v, j in L :
        heappush(q, [v, j])
    heappush(q, [P[i], i])

for i in range(N) :
    for _ in range(2-len(dpl[i])) :
        dpl[i].append(-1)
    for _ in range(2-len(dpr[i])) :
        dpr[i].append(N)
    dpl[i].sort()
    dpr[i].sort()

ret = 0
for i in range(N) :
    ret += (dpl[i][1]-dpl[i][0]) * (dpr[i][0]-i) * P[i]
    ret += (i-dpl[i][1]) * (dpr[i][1] - dpr[i][0]) * P[i]

print(ret)

Solution (Python):


from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    
    
    
    
    
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        
        
        
        
        inf = float("inf")
        self.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 << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                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):  
        layer1, layer0 = self.layer1, self.layer0

        
        y = self.rand_y
        
        
        
        y ^= (y & 0x7ffff) << 13
        y ^= y >> 17
        y ^= (y & 0x7ffffff) << 5
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

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

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

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

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

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

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


def main():
    
    inf = float("inf")
    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])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

Solution (Python):


from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    
    
    
    
    
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        
        
        
        
        inf = float("inf")
        self.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 << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                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):  
        layer1, layer0 = self.layer1, self.layer0

        
        y = self.rand_y
        
        
        
        y ^= y % 0x80000 * 0x2000
        y ^= y // 0x20000
        y ^= y % 0x8000000 * 0x20
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

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

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

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

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

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

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


def main():
    
    inf = float("inf")
    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])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

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

from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    
    
    
    
    
    def __init__(self, values=None, sorted_=False, square=1000, seed=1000000007):
        
        
        
        
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            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 = self.rand_y
                y ^= y << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                self.rand_y = y
                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):  
        layer1, layer0 = self.layer1, self.layer0

        
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

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

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

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

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

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

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


def main():
    
    inf = float("inf")
    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])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

Solution (Python):

from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    
    
    
    
    
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        
        
        
        
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y = self.rand_y
                y ^= y << 13 & 0xffffffff
                y ^= y >> 17
                y ^= y << 5 & 0xffffffff
                self.rand_y = y
                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):  
        layer1, layer0 = self.layer1, self.layer0

        
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y

        if y % self.square == 0:
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

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

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

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

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

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

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


def main():
    
    inf = float("inf")
    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])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()