Buggy python submission (verdict: Time Limit Exceeded):
class Nil:
    def __init__(self):
        self.key = 'nil'
        self.color = 'black'
        self.left = None
        self.right = None


class Node:
    def __init__(self, key=None, color='red',
                     parent=None, left=None, right=None):
        self.key = key
        self.color = color
        self.parent = parent
        self.left = left
        self.right = right


class RB:
    def __init__(self):
        self.root = Node(color='black')
        self.root.parent = Nil()
        self.root.parent.left = self.root
        
    def insert(self, key):
        if self.root.key is None:
            self.root.key = key
            return
        
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return
            
            p = cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
                
        new_node = Node(key)
        new_node.parent = p
        if new_node.key < p.key:
            p.left = new_node
            way = 'l'
        else:
            p.right = new_node
            way = 'r'
            
        self.rebalance(p, way)
            
    def rebalance(self, v, dir_vw):
        while v.color == 'red':
            u = v.parent
            if v.key < u.key:
                x = u.right
                if x and x.color == 'red':
                    if u != self.root:
                        u.color = 'red'
                    v.color = 'black'
                    x.color = 'black'
                else:
                    if dir_vw == 'l':
                        self.rotate_r(u, v)
                        return
                    else:
                        self.rotate_lr(u, v)
                        return
            else:
                x = u.left
                if x and x.color == 'red':
                    if u != self.root:
                        u.color = 'red'
                    x.color = 'black'
                    v.color = 'black'
                else:
                    if dir_vw == 'r':
                        self.rotate_l(u, v)
                        return
                    else:
                        self.rotate_rl(u, v)
                        return
            dir_vw = self.get_way(u.parent, u)
            v = u.parent 

    def rotate_r(self, u, v, d=False):
        w = v.left
        v.left = v.right
        v.right = u.right        
        if v.right:
            v.right.parent = v
        
        w.parent = u
        
        u.left = w
        u.right = v
        u.key, v.key = v.key, u.key
        
        if d:
            w.color = 'black'
        
    def rotate_lr(self, u, v, d=False):
        w = v.right
        v.right = w.left
        if v.right:
            v.right.parent = v
        
        w.left = w.right
        w.right = u.right
        if w.right:
            w.right.parent = w
        w.parent = u
        
        u.right = w
        u.key, w.key = w.key, u.key
        
        if d:
            w.color = 'black'
        
    def rotate_l(self, u, v, d=False):
        w = v.right
        
        v.right = v.left
        v.left = u.left
        if v.left:
            v.left.parent = v

        w.parent = u
        
        u.right = w
        u.left = v
        u.key, v.key = v.key, u.key
        
        if d:
            w.color = 'black'
        
    def rotate_rl(self, u, v, d=False):
        w = v.left
        
        v.left = w.right
        if v.left:
            v.left.parent = v
        
        w.right = w.left
        w.left = u.left
        if w.left:
            w.left.parent = w
        w.parent = u
        
        u.left = w
        u.key, w.key = w.key, u.key
        
        if d:
            w.color = 'black'
            
    def get_way(self, u, v):
        if u.left == v:
            return 'l'
        else:
            return 'r'
        
    def find(self, key):
        if self.root.key is None:
            return None
        
        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_smaller_key(self, cursor):
#        cursor = self.find(key)
        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.key != 'nil' and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        return None
          
    def next_greater_key(self, cursor):
#        cursor = self.find(key)
        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.key != 'nil' and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        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 = RB()
    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()

Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import insort_left, bisect_left
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
S = [0, idx[N], N+1]
total = 0
for j in range(N - 1, 0, -1):
    n = idx[j]
    i = bisect_left(S, n)
    insort_left(S, n)
    
    l1_idx = S[i-1]
    l1 = n - l1_idx
    if l1_idx != 0:
        l2_idx = S[i-2]
        l2 = l1_idx - l2_idx
    else:
        l2 = 0
        
    r1_idx = S[i+1]
    r1 = r1_idx - n
    if r1_idx != N + 1:
        r2_idx = S[i+2]
        r2 = r2_idx - r1_idx
    else:
        r2 = 0
        
    cnt = (l1 * r2 + r1 * l2) * j
    total += cnt

print(total)

Fixed submission:
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()