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



Sample input:
3
2 3 1


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    L, R = dict(), dict()
    L[pindex[N-1]] = -1
    R[pindex[N-1]] = N
    L[-1] = L[N] = -1
    R[-1] = R[N] = N
    Ans = 0
    if N == 10 ** 5:
        appeared = []
        appeared.append(-1)
        appeared.append(pindex[N - 1])
        appeared.append(N)
    
        for i in reversed(range(N - 1)):
            pid = pindex[i]
            mid = bisect(appeared, pindex[i])
            L[pid], R[pid] = appeared[mid - 1], appeared[mid]
            Ans += (i + 1) * ((pid - L[pid]) * (R[R[pid]] - R[pid]) + (R[pid] - pid) * (L[pid] - L[L[pid]]))
            appeared.insert(mid, pindex[i])
            R[L[pid]] = L[R[pid]] = pid
 
    else:
        Ans = 0
        T = AVLTree()
        T.insert(pindex[N-1])
        for i in reversed(range(N-1)):
            pid = pindex[i]
            L[pid], R[pid] = T.search(pid, -1, N)
            Ans += (i + 1) * ((pid - L[pid]) * (R[R[pid]] - R[pid]) + (R[pid] - pid) * (L[pid] - L[L[pid]]))
            T.insert(pid)
            R[L[pid]] = L[R[pid]] = pid

    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])
    L, R = dict(), dict()
    L[pindex[N-1]] = -1
    R[pindex[N-1]] = N
    L[-1] = L[N] = -1
    R[-1] = R[N] = N
    for i in reversed(range(N-1)):
        pid = pindex[i]
        L[pid], R[pid] = T.search(pid, -1, N)
        Ans += (i + 1) * ((pid - L[pid]) * (R[R[pid]] - R[pid]) + (R[pid] - pid) * (L[pid] - L[L[pid]]))
        T.insert(pid)
        R[L[pid]] = L[R[pid]] = pid
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])
    L, R = dict(), dict()
    L[pindex[N-1]] = -1
    R[pindex[N-1]] = N
    L[-1] = L[N] = -1
    R[-1] = R[N] = N
    for i in reversed(range(N-1)):
        pid = pindex[i]
        left, right = T.search(pid, -1, N)
        Ans += (i + 1) * ((pid - left) * (R[right] - right) + (right - pid) * (left - L[left]))
        T.insert(pid)
        L[pid], R[pid] = left, right
        R[left] = L[right] = pid
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])
    L, R = dict(), dict()
    L[pindex[N-1]] = -1
    R[pindex[N-1]] = N
    L[-1], R[-1] = -1, N
    L[N], R[N] = -1, N
    for i in reversed(range(N-1)):
        pid = pindex[i]
        left, right = T.search(pid, -1, N)
        l2, r2 = L[left], R[right]
        Ans += (i + 1) * ((pid - left) * (r2 - right) + (right - pid) * (left - l2))
        T.insert(pid)
        L[pid], R[pid] = left, right
        R[left], L[right] = pid, pid
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, key, height):
        self.key = key
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])
    for i in reversed(range(N-1)):
        pid = pindex[i]
        left, right = T.search(pid, -1, N)
        l2 = T.lower_bound(left, -1)
        r2 = T.upper_bound(right, N)
        Ans += (i + 1) * ((pid - left) * (r2 - right) + (right - pid) * (left - l2))
        T.insert(pid)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])
    for i in reversed(range(N-1)):
        pid = pindex[i]
        left, right = T.search(pid, -1, N)
        l2 = T.lower_bound(left, -1)
        r2 = T.upper_bound(right, N)
        Ans += (i + 1) * ((pid - left) * (r2 - right) + (right - pid) * (left - l2))
        T.insert(pid)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])
    for i in reversed(range(N-1)):
        pid = pindex[i]
        left, right = T.search(pid, -1, N)
        if left <= 0: l2 = -1
        else: l2 = T.lower_bound(left, -1)
        if right >= N - 1: r2 = N
        else: r2 = T.upper_bound(right, N)
        Ans += (i + 1) * ((pid - left) * (r2 - right) + (right - pid) * (left - l2))
        T.insert(pid)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])
    for i in reversed(range(N-1)):
        pid = pindex[i]
        left, right = T.lower_bound(pid, -1), T.upper_bound(pid, N)
        if left <= 0: l2 = -1
        else: l2 = T.lower_bound(left, -1)
        if right >= N - 1: r2 = N
        else: r2 = T.upper_bound(right, N)
        Ans += (i + 1) * ((pid - left) * (r2 - right) + (right - pid) * (left - l2))
        T.insert(pid)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()