Problem:
 Score: 500 points    Problem Statement  Given is a permutation P of \{1, 2, \ldots, N\} .  For a pair (L, R) (1 \le L \lt R \le N) , let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R .  Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R} .      Constraints   2 \le N \le 10^5  1 \le P_i \le N  P_i \neq P_j  (i \neq j)  All values in input are integers.         Input  Input is given from Standard Input in the following format:  N  P_1  P_2  \ldots  P_N       Output  Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R} .        Sample Input 1 3
2 3 1      Sample Output 1 5  X_{1, 2} = 2, X_{1, 3} = 2 , and X_{2, 3} = 1 , so the sum is 2 + 2 + 1 = 5 .       Sample Input 2 5
1 2 3 4 5      Sample Output 2 30       Sample Input 3 8
8 2 7 3 4 5 6 1      Sample Output 3 136

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

N=int(input())
p=list(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):

ans=0
n=int(input())
p=list(map(int,input().split()))
b=[0]*(n+1)
for i in range(n):
    b[p[i]]=i+1
LL=[0]+[i for i in range(n+1)]
RR=[i for i in range(1,n+2)]+[n+1]
for i in range(1,n+1):
    l1=LL[b[i]]
    l0=LL[l1]
    r0=RR[b[i]]
    r1=RR[r0]
    ans+=((l1-l0)*(r0-b[i])+(r1-r0)*(b[i]-l1))*i
    LL[r0]=l1
    RR[l1]=r0

print(ans)

Solution (Python):
class BIT(object):
    from operator import add
    def __init__(self,A,f=add):
        N=len(A)
        self.__len=N
        self.__f=f
        
        self.__bit=A[:] 
        for i in range(N):
            j=i+((i+1)&-(i+1))
            if j<N: self.tree[j]=self.func(self.tree[i],self.tree[j])

    def __repr__(self):
        return str(self.tree)

    @property
    def func(self):
        return self.__f

    @property
    def tree(self): 
        return self.__bit

    def add(self,i,w):
        while(i<self.__len):
            self.tree[i]=self.func(self.tree[i],w)
            i+=(i+1)&-(i+1)

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

    def bisect_left(self,w):
        
        if w>self.sum(self.__len-1): return self.__len
        
        elif self.__len==1: return 0
        
        n=2**((self.__len-1).bit_length()-1)
        res=0
        while(n):
            if res+n-1>self.__len-1: 
                n//=2
                continue
            if w<=self.tree[res+n-1]: 
                n//=2
            else: 
                w-=self.tree[res+n-1]
                res+=n
                n//=2
        return res

    def bisect_right(self,w):
        if w>=self.sum(self.__len-1): return self.__len
        elif self.__len==1: return 0
        n=2**((self.__len-1).bit_length()-1)
        res=0
        while(n):
            if w<self.tree[res+n-1]:
                n//=2
            else:
                w-=self.tree[res+n-1]
                res+=n
                n//=2
        return res


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

idx=[0]*n
for i,a in enumerate(A): idx[a-1]=i


bit=BIT([0]*n)


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

Solution (Python):
class WeightBalancedTree:
    def __init__(self, q):
        self.left = [0] * (q + 1)
        self.right = [0] * (q + 1)
        self.weight = [1] * (q + 1)
        self.key = [None] * (q + 1)
        self.last_index = 0
        self.root = 0


    def search_lower(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] < key:
                ret = self.key[idx]
                idx = self.right[idx]
            else:
                idx = self.left[idx]
        return ret


    def search_higher(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] > key:
                ret = self.key[idx]
                idx = self.left[idx]
            else:
                idx = self.right[idx]
        return ret




    def insert(self, key):
        self.last_index += 1
        self.key[self.last_index] = key
        self.weight[self.last_index] = 2
        self.root = self.__recursive_insert(self.root)


    def __recursive_insert(self, idx):
        if idx == 0:
            return self.last_index
        elif self.key[self.last_index] < self.key[idx]:
            self.left[idx] = self.__recursive_insert(self.left[idx])
            self.__fix(idx)
            return self.__fix_left_bias(idx)
        else:
            self.right[idx] = self.__recursive_insert(self.right[idx])
            self.__fix(idx)
            return self.__fix_right_bias(idx)


    def __fix(self, idx):
        self.weight[idx] = self.weight[self.left[idx]] + \
            self.weight[self.right[idx]]


    def __rotate_left(self, idx):
        right = self.right[idx]
        self.right[idx] = self.left[right]
        self.__fix(idx)
        self.left[right] = idx
        self.__fix(right)
        return right


    def __rotate_right(self, idx):
        left = self.left[idx]
        self.left[idx] = self.right[left]
        self.__fix(idx)
        self.right[left] = idx
        self.__fix(left)
        return left


    def __fix_left_bias(self, idx):
        if self.weight[self.right[idx]] << 2 < self.weight[idx]:
            left = self.left[idx]
            if self.weight[self.left[left]] << 2 < self.weight[left]:
                self.left[idx] = self.__rotate_left(left)
            idx = self.__rotate_right(idx)
        return idx


    def __fix_right_bias(self, idx):
        if self.weight[self.left[idx]] << 2 < self.weight[idx]:
            right = self.right[idx]
            if self.weight[self.right[right]] << 2 < self.weight[right]:
                self.right[idx] = self.__rotate_right(right)
            idx = self.__rotate_left(idx)
        return idx


    def size(self):
        return self.weight[self.root] - 1


    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx != 0:
            self.__dump(self.right[idx], dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print('i:{0},k:{1},l:{2},r:{3},w:{4}'.format(
                idx, self.key[idx], self.left[idx], self.right[idx], self.weight[idx]))
            self.__dump(self.left[idx], dep + 1)


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 = WeightBalancedTree(n+2)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(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):
class AvlTree:  
    def __init__(self, values=None, sorted_=False, n=0):
        
        
        

        
        
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  
                l, r, idx_par = st.pop()  
                c = (l + r) >> 1  
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            
            self_size_l[idx] -= self_size_l[idx_l] + 1

            
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  

    def rotate_left(self, idx_par, lr):  
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            
            self_size_l[idx_r] += self_size_l[idx] + 1

            
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  

    def add(self, x):  
        
        
        

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  
                return False  

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  
        
        

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  
                idx = self_left[idx]
            else:  
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  
            
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  
            
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        
        

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  
            
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  
            
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  
        

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  
        return False

    def bisect_left(self, x):  
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

N = int(input())
P = list(map(int, input().split()))
I = [-1] * (N+1)
for i, p in enumerate(P):
    I[p] = i
ans = 0
avl = AvlTree(n=N)
for val, (n, idx) in zip(range(N, 0, -1), enumerate(I[N:0:-1], 1)):
    avl.add(idx)
    idx_avl = avl.bisect_left(idx)  
    l = avl[idx_avl-1] if idx_avl>0 else -1
    r = avl[idx_avl+1] if idx_avl<n-1 else N
    
    if idx_avl > 0:
        l2 = avl[idx_avl-2] if idx_avl>1 else -1
        ans += val * (l-l2) * (r-idx)
        
    if idx_avl < n-1:
        r2 = avl[idx_avl+2] if idx_avl<n-2 else N
        ans += val * (idx-l) * (r2-r)
        
print(ans)

Solution (Python):
class WeightBalancedTree:
    def __init__(self, q):
        self.left = [0] * (q + 1)
        self.right = [0] * (q + 1)
        self.weight = [1] * (q + 1)
        self.key = [None] * (q + 1)
        self.last_index = 0
        self.root = 0


    def search_lower(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] < key:
                ret = self.key[idx]
                idx = self.right[idx]
            else:
                idx = self.left[idx]
        return ret


    def search_higher(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] > key:
                ret = self.key[idx]
                idx = self.left[idx]
            else:
                idx = self.right[idx]
        return ret




    def insert(self, key):
        self.last_index += 1
        self.key[self.last_index] = key
        self.weight[self.last_index] = 2
        self.root = self.__recursive_insert(self.root)
        NotImplemented


    def __recursive_insert(self, idx):
        if idx == 0:
            return self.last_index
        elif self.key[self.last_index] < self.key[idx]:
            self.left[idx] = self.__recursive_insert(self.left[idx])
            self.__fix(idx)
            return self.__fix_left_bias(idx)
        else:
            self.right[idx] = self.__recursive_insert(self.right[idx])
            self.__fix(idx)
            return self.__fix_right_bias(idx)


    def __fix(self, idx):
        self.weight[idx] = self.weight[self.left[idx]] + \
            self.weight[self.right[idx]]


    def __rotate_left(self, idx):
        right = self.right[idx]
        self.right[idx] = self.left[right]
        self.__fix(idx)
        self.left[right] = idx
        self.__fix(right)
        return right


    def __rotate_right(self, idx):
        left = self.left[idx]
        self.left[idx] = self.right[left]
        self.__fix(idx)
        self.right[left] = idx
        self.__fix(left)
        return left


    def __fix_left_bias(self, idx):
        if self.weight[self.right[idx]] << 2 < self.weight[idx]:
            left = self.left[idx]
            if self.weight[self.left[left]] << 2 < self.weight[left]:
                self.left[idx] = self.__rotate_left(left)
            idx = self.__rotate_right(idx)
        return idx


    def __fix_right_bias(self, idx):
        if self.weight[self.left[idx]] << 2 < self.weight[idx]:
            right = self.right[idx]
            if self.weight[self.right[right]] << 2 < self.weight[right]:
                self.right[idx] = self.__rotate_right(right)
            idx = self.__rotate_left(idx)
        return idx


    def size(self):
        return self.weight[self.root] - 1


    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx != 0:
            self.__dump(self.right[idx], dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print('i:{0},k:{1},l:{2},r:{3},w:{4}'.format(
                idx, self.key[idx], self.left[idx], self.right[idx], self.weight[idx]))
            self.__dump(self.left[idx], dep + 1)


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 = WeightBalancedTree(n+2)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(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):
class WeightBalancedTree:
    def __init__(self, q):
        self.left = [0] * (q + 1)
        self.right = [0] * (q + 1)
        self.weight = [1] * (q + 1)
        self.key = [None] * (q + 1)
        self.last_index = 0
        self.root = 0


    def search_lower(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] < key:
                ret = self.key[idx]
                idx = self.right[idx]
            else:
                idx = self.left[idx]
        return ret


    def search_higher(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] > key:
                ret = self.key[idx]
                idx = self.left[idx]
            else:
                idx = self.right[idx]
        return ret




    def insert(self, key):
        self.last_index += 1
        self.key[self.last_index] = key
        self.weight[self.last_index] = 2
        self.root = self.__recursive_insert(self.root)
        NotImplemented


    def __recursive_insert(self, idx):
        if idx == 0:
            return self.last_index
        elif self.key[self.last_index] < self.key[idx]:
            self.left[idx] = self.__recursive_insert(self.left[idx])
            self.__fix(idx)
            return self.__fix_left_bias(idx)
        else:
            self.right[idx] = self.__recursive_insert(self.right[idx])
            self.__fix(idx)
            return self.__fix_right_bias(idx)


    def __fix(self, idx):
        self.weight[idx] = self.weight[self.left[idx]] + \
            self.weight[self.right[idx]]


    def __rotate_left(self, idx):
        right = self.right[idx]
        self.right[idx] = self.left[right]
        self.__fix(idx)
        self.left[right] = idx
        self.__fix(right)
        return right


    def __rotate_right(self, idx):
        left = self.left[idx]
        self.left[idx] = self.right[left]
        self.__fix(idx)
        self.right[left] = idx
        self.__fix(left)
        return left


    def __fix_left_bias(self, idx):
        if self.weight[self.right[idx]] * 4 < self.weight[idx]:
            left = self.left[idx]
            if self.weight[self.left[left]] * 4 < self.weight[left]:
                self.left[idx] = self.__rotate_left(left)
            idx = self.__rotate_right(idx)
        return idx


    def __fix_right_bias(self, idx):
        if self.weight[self.left[idx]] * 4 < self.weight[idx]:
            right = self.right[idx]
            if self.weight[self.right[right]] * 4 < self.weight[right]:
                self.right[idx] = self.__rotate_right(right)
            idx = self.__rotate_left(idx)
        return idx


    def size(self):
        return self.weight[self.root] - 1


    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx != 0:
            self.__dump(self.right[idx], dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print('i:{0},k:{1},l:{2},r:{3},w:{4}'.format(
                idx, self.key[idx], self.left[idx], self.right[idx], self.weight[idx]))
            self.__dump(self.left[idx], dep + 1)


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 = WeightBalancedTree(n+2)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(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()