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 defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n = II()
    print(n**3)
    return


def B():
    n = II()
    a = LI()
    b = LI()
    c = LI()
    ans = 0
    for i in range(n):
        ans += b[a[i] - 1] + (c[a[i] - 1] if i != n - 1 and a[i] + 1 == a[i + 1] else 0)
    print(ans)
    return


def C():
    n = II()
    b = LI()
    ans = b[0]
    for i in range(n-2):
        if b[i] >= b[i + 1]:
            ans += b[i + 1]
        else:
            ans += b[i]
    print(ans+b[-1])
    return


def D():
    n, k = LI()
    s = S()
    a = []
    for i in range(n):
        if i == n - 1:
            a.append(s[i])
        elif s[i] != s[i + 1]:
            a.append(s[i])
    print(min(n - 1, n - len(a) + 2 * k))
    return













class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i
        while x < self.size:
            self.bit[x] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i
        while x > 0:
            res += self.bit[x]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        ok = self.size
        ng = 0
        while abs(ok - ng) != 1:
            mid = (ok + ng)//2
            if self.sum(mid) >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def __len__(self):
        return self.size

def E():
    n = II()
    a = LI()
    dic = defaultdict(int)
    for i, ai in enumerate(a):
        dic[ai] = i+1
    bit = BinaryIndexedTree(n+1)
    num = [i + 1 for i in range(n)][::-1]
    ans = 0
    for i in num:
        c = dic[i]
        L = bit.sum(c)
        bit.add(c,1)
        R = n-i-L 
        a = bit.search(L-1) if L >= 2 else 0
        b = bit.search(L) if L >= 1 else 0
        d = bit.search(L+2) if R >= 1 else n+1
        e = bit.search(L+3) if R >= 2 else n+1
        tmp = 0
        if b != 0:
            tmp += (b-a) * (d-c)
        if d != 0:
            tmp += (e-d) * (c-b)
        ans += i * tmp

    print(ans)
    return


def F():
    return



if __name__ == '__main__':
    E()

Solution (Python):
class Node:
    def __init__(self, key=None):
        self.key = key
        self.balance = 'E'
        self.parent = None
        self.left = None
        self.right = None


class AVL:
    def __init__(self):
        self.root = Node()
        self.root.parent = Node('nil')

    def insert(self, key):
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node
            
        return self.rebalance(p, new_node, key)
            
    def rebalance(self, u, v, key):
        while u.key != 'nil':
            if u.key > v.key:
                if u.balance == 'R':
                    u.balance = 'E'
                    return
                elif u.balance == 'L':
                    if v.balance == 'L':
                        self.rotate_R(u, v)
                        return
                    elif v.balance == 'R':

                        self.rotate_LR(u, v)
                        return
                else:
                    u.balance = 'L'
                    v = u
                    u = u.parent
            else:
                if u.balance == 'L':
                    u.balance = 'E'
                    return
                elif u.balance == 'R':
                    if v.balance == 'R':
                        self.rotate_L(u, v)
                        return
                    elif v.balance == 'L':
                        self.rotate_RL(u, v)
                        return
                else:
                    u.balance = 'R'
                    v = u
                    u = u.parent
              
    def replace(self, u, v):
        if u.parent.left == u:
            u.parent.left = v
        else:
            u.parent.right = v
        v.parent = u.parent
        if v.parent.key == 'nil':
            self.root = v   

    def rotate_R(self, u, v):
        w = v.right

        self.replace(u, v)
        v.right = u
        u.parent = v        
        u.left = w        
        if w:
            w.parent = u
        u.balance = 'E'
        v.balance = 'E'           

    def rotate_L(self, u, v):
        w = v.left
        
        self.replace(u, v)
        v.left = u
        u.parent = v
        u.right = w        
        if w:
            w.parent = u
        u.balance = 'E'
        v.balance = 'E' 

    def rotate_LR(self, u, v):
        w = v.right
        
        self.replace(u, w)
        if w.left:
            v.right = w.left
            v.right.parent = v
        else:
            v.right = None
        if w.right:
            u.left = w.right
            u.left.parent = u
        else:
            u.left = None
        v.parent = w
        w.left = v
        u.parent = w
        w.right = u

        if w.balance == 'R':
            u.balance = 'E'
            v.balance = 'L'
        elif w.balance == 'L':
            u.balance ='R'
            v.balance = 'E'
        else:
            u.balance = 'E'
            v.balance = 'E'
        w.balance = 'E'        

    def rotate_RL(self, u, v):
        w = v.left
        
        self.replace(u, w)
        if w.left:
            w.left.parent = u
            u.right = w.left
        else:
            u.right = None
        if w.right:
            w.right.parent = v
            v.left = w.right
        else:
            v.left = None
        u.parent = w
        w.left = u
        v.parent = w
        w.right = v       
        
        if w.balance == 'R':
            u.balance = 'L'
            v.balance = 'E'
        elif w.balance == 'L':
            u.balance ='E'
            v.balance = 'R'
        else:
            u.balance = 'E'
            v.balance = 'E'
        w.balance = 'E'

    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent.key != 'nil' and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return 
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent.key != 'nil' and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2


def main():

    import sys




    
    input = sys.stdin.readline
    N = int(input())
    P = map(int, input().split())    
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
if __name__ == '__main__':
    main()

Solution (Python):
class Node:
    def __init__(self,  key=None):

        self.key = key
        self.height = 1
        self.parent = None
        self.left = None
        self.right = None


def update_height(t):
    if t.left is not None:
        l = t.left.height
    else:
        l = 0
    if t.right is not None:
        r = t.right.height
    else:
        r = 0
    
    if l >= r:
        t.height = l + 1
    else:
        t.height = r + 1


class AVL:
    def __init__(self):
        self.root = Node()       
    
    def insert(self, key):
        
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node

        
        cursor = p
        while cursor:
            if cursor.left is not None:
                l = cursor.left.height
            else:
                l = 0
            if cursor.right is not None:
                r = cursor.right.height
            else:
                r = 0
            balance = l - r
            
            if balance == 0:
                break
            elif balance == 2:
                if key < cursor.left.key:
                    self.rotate_r(cursor)
                else:
                    self.rotate_lr(cursor)
                break
            elif balance == -2:
                if key > cursor.right.key:
                    self.rotate_l(cursor)
                else:
                    self.rotate_rl(cursor)
                break
            else:
                update_height(cursor)
                cursor = cursor.parent
           
    def rotate_r(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc is not None:
            n.left = gc
            gc.parent = n
        else:
            n.left = None
            
        c.right = n
        n.parent = c
        
        if p is not None:    
            if p.right == n:
                p.right = c
            else:
                p.left = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)
    
    def rotate_l(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc is not None:
            n.right = gc
            gc.parent = n
        else:
            n.right = None
            
        c.left = n
        n.parent = c
        
        if p is not None:
            if p.left == n:
                p.left = c
            else:
                p.right = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
        
        update_height(n)
        update_height(c)              
        
    def rotate_rl(self, n):
        
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc.left and gc.right:
            n.right = gc.left
            c.left = gc.right
            gc.left.parent = n
            gc.right.parent = c
        elif gc.left:
            n.right = gc.left
            gc.left.parent = n
            c.left = None
        elif gc.right:
            c.left = gc.right
            gc.right.parent = c
            n.right = None
        else:
            n.right = None
            c.left = None
            
        gc.left = n
        gc.right = c
        n.parent = gc
        c.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None

        update_height(n)
        update_height(c)
        update_height(gc)        
        
    def rotate_lr(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc.left and gc.right:
            c.right = gc.left
            n.left = gc.right
            gc.left.parent = c
            gc.right.parent = n
        elif gc.left:
            c.right = gc.left
            gc.left.parent = c
            n.left = None
        elif gc.right:
            n.left = gc.right
            gc.right.parent = n
            c.right = None
        else:
            n.left = None
            c.right = None
        gc.left = c
        gc.right = n
        c.parent = gc
        n.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)    
        
    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return None
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return None
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent              
        else:
            return None
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2


def main():

    N = int(input())
    P = map(int, input().split())
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
if __name__ == '__main__':
    main()

Solution (Python):
class Node:
    def __init__(self,  key=None):
        self.key = key
        self.height = 1
        self.parent = None
        self.left = None
        self.right = None

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

def get_balance(t):
    return get_height(t.left) - get_height(t.right)

def update_height(t):
    left_height = get_height(t.left)
    right_height = get_height(t.right)
    if left_height >= right_height:
        t.height = left_height + 1
    else:
        t.height = right_height + 1


class AVL:
    def __init__(self):
        self.root = Node()       
    
    def insert(self, key):
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node
        
        cursor = p
        while cursor:     
            balance = get_balance(cursor)
            if balance == 0:
                break
            elif balance == 2:
                if key < cursor.left.key:
                    self.rotate_r(cursor)
                else:
                    self.rotate_lr(cursor)
                break
            elif balance == -2:
                if key > cursor.right.key:
                    self.rotate_l(cursor)
                else:
                    self.rotate_rl(cursor)
                break
            else:
                update_height(cursor)
                cursor = cursor.parent
           
    def rotate_r(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc is not None:
            n.left = gc
            gc.parent = n
        else:
            n.left = None
            
        c.right = n
        n.parent = c
        
        if p is not None:    
            if p.right == n:
                p.right = c
            else:
                p.left = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)                
    
    def rotate_l(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc is not None:
            n.right = gc
            gc.parent = n
        else:
            n.right = None
            
        c.left = n
        n.parent = c
        
        if p is not None:
            if p.left == n:
                p.left = c
            else:
                p.right = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)       
      
    def rotate_rl(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc.left and gc.right:
            n.right = gc.left
            c.left = gc.right
            gc.left.parent = n
            gc.right.parent = c
        elif gc.left:
            n.right = gc.left
            gc.left.parent = n
            c.left = None
        elif gc.right:
            c.left = gc.right
            gc.right.parent = c
            n.right = None
        else:
            n.right = None
            c.left = None
            
        gc.left = n
        gc.right = c
        n.parent = gc
        c.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)

    def rotate_lr(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc.left and gc.right:
            c.right = gc.left
            n.left = gc.right
            gc.left.parent = c
            gc.right.parent = n
        elif gc.left:
            c.right = gc.left
            gc.left.parent = c
            n.left = None
        elif gc.right:
            n.left = gc.right
            gc.right.parent = n
            c.right = None
        else:
            n.left = None
            c.right = None
        gc.left = c
        gc.right = n
        c.parent = gc
        n.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)        
        
    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return None
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return None
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent              
        else:
            return None
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2
                

def main():

    N = int(input())
    P = map(int, input().split())
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
if __name__ == '__main__':
    main()

Solution (Python):

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

r = list(range(n))
l = list(range(n))
I = [-1] * (n+1)

for i,P in enumerate(p):
	I[P] = i


ans  = 0

for N,index in enumerate(I[1:],1):
	L = index -1
	if L >= 0:
		L = l[L]

	R = index + 1
	if  R < n:
		R = r[R]

	l[R-1] = L
	r[L+1] = R

	if L >= 0:
		L2 = L-1
		if L2 >= 0:
			L2 = l[L2]
		ans += N * (L-L2) * (R - index)

	if R < n:
		R2 = R+1
		if R2 < n:
			R2 = r[R2]
		ans += N * (index - L ) * (R2 - R)
print(ans)

Solution (Python):
class MinSegmentTree():
    def __init__(self, n):
        self.n = n
        self.INF = n - 1
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = min(self.node[2*i + 1], self.node[2*i + 2])

    def get_min(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = min(s, self.node[end])
            if (begin - 1) & 1:
                s = min(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s

class MaxSegmentTree():
    def __init__(self, n):
        self.n = n
        self.INF = 0
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = max(self.node[2*i + 1], self.node[2*i + 2])

    def get_max(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = max(s, self.node[end])
            if (begin - 1) & 1:
                s = max(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s


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

ind = {}
for i in range(n):
    ind[a[i]] = i
smax = MaxSegmentTree(n+2)
smin = MinSegmentTree(n+2)

ans = 0
for i in range(n):
    pos = ind[n-i] + 1
    l2 = smax.get_max(0, pos)
    l1 = smax.get_max(0, l2)
    r1 = smin.get_min(pos+1, n+2)
    r2 = smin.get_min(r1+1, n+2)
    smin.update(pos, pos)
    smax.update(pos, pos)
    ans += ((l2 - l1) * (r1 - pos) + (r2 - r1) * (pos - l2)) * (n-i)
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,*P = map(int,read().split())

INF = N+100
P = [INF,INF] + P + [INF,INF]

x_to_i = [0] * (INF+1)
for i,x in enumerate(P):
    x_to_i[x] = i

"""
・小さい方から埋めていく。
・埋めた位置に対して、「連結成分の左端」「連結成分の右端」を持つ
・区間の両端については、正しい値が入っている状態を保つ
"""

left = list(range(N+4))
right = list(range(N+4))
filled = [False] * (N+4)

answer = 0
for x,i in enumerate(x_to_i[1:N+1],1):
    filled[i] = True
    L = left[i-1] if filled[i-1] else i
    R = right[i+1] if filled[i+1] else i
    right[L] = R; left[R] = L
    
    c = i
    b = L-1; d = R+1
    a = left[L-2]-1 if filled[L-2] else L-2
    e = right[R+2]+1 if filled[R+2] else R+2
    coef = 0
    if b>=2: 
        coef += (b-a)*(d-c)
    if d<=N+1:
        coef += (e-d)*(c-b)
    answer += x*coef

print(answer)

Solution (Python):

import sys
N=input()


bit=[ 0 for i in range(N+1) ]
bit[0]=None


def add(x,w):
	while x<=N:
		bit[x]+=w
		x+=x&(-1*x)

def bitsum(x):
	s=0
	while 0<x:
		s+=bit[x]
		x-=x&(-1)*x
	return s

def search(wa):
	if wa<=0: return 0
	if bitsum(N)<wa: return N+1
	r=N
	l=0
	while r-l!=1:
		m=(l+r)/2
		if bitsum(m)<wa:
			l=m
		else:
			r=m	
	return r



A=map(int, sys.stdin.readline().split())

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

ans=0

x=N
add(B[x],1)


for x in range(N-1,0,-1):
	cur_p=B[x]	
	cur_v=bitsum(cur_p)
	l1=search(cur_v)
	l2=search(cur_v-1)
	r1=search(cur_v+1)
	r2=search(cur_v+2)
	
	
	
	ans+=( (l1-l2)*(r1-cur_p)+(cur_p-l1)*(r2-r1) )*x
	
	add(B[x],1)

print ans

Solution (Python):

import sys
N=input()


bit=[ 0 for i in range(N+1) ]
bit[0]=None


def add(x,w):
	while x<=N:
		bit[x]+=w
		x+=x&(-1*x)

def bitsum(x):
	s=0
	while 0<x:
		s+=bit[x]
		x-=x&(-1)*x
	return s

def search(wa):
	if wa<=0: return 0
	if bitsum(N)<wa: return N+1
	r=N
	l=0
	while r-l!=1:
		m=(l+r)/2
		if bitsum(m)<wa:
			l=m
		else:
			r=m	
	return r



A=map(int, sys.stdin.readline().split())

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

ans=0
x=N
add(B[x],1)


for x in range(N-1,0,-1):
	cur_p=B[x]	
	cur_v=bitsum(cur_p)
	l1=search(cur_v)
	l2=search(cur_v-1)
	r1=search(cur_v+1)
	r2=search(cur_v+2)
	
	
	
	ans+=( (l1-l2)*(r1-cur_p)+(cur_p-l1)*(r2-r1) )*x
	
	add(B[x],1)

print ans