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: Runtime Error

Solution code:
import os
import sys

import numpy as np


# Global variables
# N is large enough size to store nodes at one time.
# children: ndarray(N, 2)  current [left / right] child node index
# values:   ndarray(N)     -1 is represents EOT
# colors:   ndarray(N)     0:black 1:red
# counts:   ndarray(N)     number of nodes in subtree
# available: set           available indices, set(range(N)) at initial
# root:      int           root index, 0 at initial


def solve(inp):
    RBT_SIZE = 20
    RBT_EOT = -2
    RBT_AVAILABLE_INDICES = set(range(RBT_SIZE - 1))
    RBT_CHILDREN = np.zeros((RBT_SIZE, 2), dtype=np.int64)
    RBT_VALUES = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_COLORS = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_COUNTS = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_ROOT = -1
    RBT_CHILDREN[RBT_ROOT, 0] = RBT_CHILDREN[RBT_ROOT, 1] = RBT_ROOT

    def _rbt_rotate(i, is_right):
        """
        Rotate node i to right if is_right=1 and left if 0.
        Return the index of new node that replaces node i.
        """
        r = is_right
        ci = RBT_CHILDREN[i, r ^ 1]
        RBT_CHILDREN[i, r ^ 1] = RBT_CHILDREN[ci, r]
        RBT_CHILDREN[ci, r] = i
        RBT_COLORS[ci] = RBT_COLORS[i]
        RBT_COLORS[i] = 1
        child_count = RBT_COUNTS[ci]
        RBT_COUNTS[ci] = RBT_COUNTS[i]
        RBT_COUNTS[i] -= child_count - RBT_COUNTS[RBT_CHILDREN[i, r ^ 1]]
        return ci

    def _rbt_balance_insert(i, is_right):
        flag = True
        r = is_right
        if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r], r ^ 1]] == 1:
            RBT_CHILDREN[i, r] = _rbt_rotate(RBT_CHILDREN[i, r], r)
        if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r], r]] == 1:
            if RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] == 1:
                RBT_COLORS[i] = 1
                RBT_COLORS[RBT_CHILDREN[i, r]] = RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 0
                flag = False
            else:
                i = _rbt_rotate(i, r ^ 1)
        return i, flag

    def _rbt_balance_delete(i, is_right):
        flag = True
        stack = [(i, is_right)]
        while stack:
            i, r = stack.pop()
            if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r]] == 0 and \
                    RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r ^ 1]] == 0:
                if RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] == 0:
                    RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 1
                    if RBT_COLORS[i] == 0:
                        flag = False
                    RBT_COLORS[i] = 0
                    break
                else:
                    i = _rbt_rotate(i, r)
                    stack.append((i, r))
                    stack.append((RBT_CHILDREN[i, r], r))
                    continue
            else:
                if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r]] == 1:
                    RBT_CHILDREN[i, r ^ 1] = _rbt_rotate(RBT_CHILDREN[i, r ^ 1], r ^ 1)
                i = _rbt_rotate(i, r)
                RBT_COLORS[RBT_CHILDREN[i, r]] = 0
                RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 0
                break

        while stack:
            pi, r = stack.pop()
            RBT_CHILDREN[pi, r] = i
            i = pi

        return i, flag

    def _rbt_get_min_in_subtree(i, stack):
        while RBT_CHILDREN[i, 0] != -1:
            stack.append((i, 0))
            i = RBT_CHILDREN[i, 0]
        return i

    def rbt_insert(root, x):
        """
        Insert value x.
        Return new root index
        """

        stack = []
        i = root
        while i != -1:
            to_right = 1 if x >= RBT_VALUES[i] else 0
            stack.append((i, to_right))
            i = RBT_CHILDREN[i, to_right]

        for pi, _ in stack:
            RBT_COUNTS[pi] += 1

        i = RBT_AVAILABLE_INDICES.pop()
        RBT_CHILDREN[i, 0] = -1
        RBT_CHILDREN[i, 1] = -1
        RBT_VALUES[i] = x
        RBT_COLORS[i] = 1
        RBT_COUNTS[i] = 1

        if stack:
            pi, r = stack[-1]
            RBT_CHILDREN[pi, r] = i

        while stack:
            pi, is_right = stack.pop()
            if RBT_COLORS[pi] == 1:
                i = pi
                continue
            RBT_CHILDREN[pi, is_right] = i
            i, flag = _rbt_balance_insert(pi, is_right)

            if stack and flag:
                pi, is_right = stack.pop()
                RBT_CHILDREN[pi, is_right] = i
                break

        else:
            RBT_COLORS[i] = 0
            return i

        return root

    def rbt_delete(root, x):
        """
        Delete value x.
        Return new root index
        """
        i = root
        stack = []
        while i != -1 and RBT_VALUES[i] != x:
            is_right = 1 if RBT_VALUES[i] < x else 0
            stack.append((i, is_right))
            i = RBT_CHILDREN[i, is_right]

        if i == -1:
            return root

        if RBT_CHILDREN[i, 0] != -1 and RBT_CHILDREN[i, 1] != -1:
            stack.append((i, 1))
            mi = _rbt_get_min_in_subtree(RBT_CHILDREN[i, 1], stack)
            RBT_COLORS[i] = RBT_COLORS[mi]
            i = mi

        for pi, _ in stack:
            RBT_COUNTS[pi] -= 1

        pi, is_right = stack[-1]
        if RBT_CHILDREN[i, 0] == -1:
            RBT_CHILDREN[pi, is_right] = RBT_CHILDREN[i, 1]
            RBT_COLORS[RBT_CHILDREN[i, 1]] = 0
            if RBT_CHILDREN[i, 1] != -1 or RBT_COLORS[i] == 1:
                return root
        elif RBT_CHILDREN[i, 1] == -1:
            RBT_CHILDREN[pi, is_right] = RBT_CHILDREN[i, 0]
            RBT_COLORS[RBT_CHILDREN[i, 0]] = 0
            return root

        while stack:
            pi, is_right = stack.pop()
            i, flag = _rbt_balance_delete(pi, is_right)

            if stack and flag:
                pi, is_right = stack.pop()
                RBT_CHILDREN[pi, is_right] = i
                break

        else:
            RBT_COLORS[i] = 0
            return i

        return root

    def rbt_upper_bound(root, x):
        i = root
        y = RBT_EOT
        c = RBT_COUNTS[i]
        j = 0
        while i != -1:
            if x < RBT_VALUES[i]:
                y = RBT_VALUES[i]
                c = j + RBT_COUNTS[RBT_CHILDREN[i, 0]]
                i = RBT_CHILDREN[i, 0]
            else:
                j += RBT_COUNTS[RBT_CHILDREN[i, 0]] + 1
                i = RBT_CHILDREN[i, 1]
        return y, c

    def rbt_lower_bound(root, x):
        i = root
        y = RBT_EOT
        c = RBT_COUNTS[i]
        j = 0
        while i != -1:
            if x <= RBT_VALUES[i]:
                y = RBT_VALUES[i]
                c = j + RBT_COUNTS[RBT_CHILDREN[i, 0]]
                i = RBT_CHILDREN[i, 0]
            else:
                j += RBT_COUNTS[RBT_CHILDREN[i, 0]] + 1
                i = RBT_CHILDREN[i, 1]
        return y, c

    def rbt_get_k_th(root, k):
        i = root
        if RBT_COUNTS[i] <= k:
            return RBT_EOT
        j = k
        while i != -1:
            left_count = RBT_COUNTS[RBT_CHILDREN[i, 0]]
            if left_count == j:
                return RBT_VALUES[i]
            elif left_count > j:
                i = RBT_CHILDREN[i, 0]
            else:
                j -= left_count + 1
                i = RBT_CHILDREN[i, 1]
        return RBT_EOT

    n = inp[0]
    ppp = inp[1:]
    idx = np.argsort(ppp)[::-1]

    RBT_ROOT = rbt_insert(RBT_ROOT, -1)
    RBT_ROOT = rbt_insert(RBT_ROOT, -1)
    RBT_ROOT = rbt_insert(RBT_ROOT, n)
    RBT_ROOT = rbt_insert(RBT_ROOT, n)

    ans = 0
    for i in idx:
        p = ppp[i]
        r1, j = rbt_upper_bound(RBT_ROOT, i)
        r2 = rbt_get_k_th(RBT_ROOT, j + 1)
        l1 = rbt_get_k_th(RBT_ROOT, j - 1)
        l2 = rbt_get_k_th(RBT_ROOT, j - 2)
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        RBT_ROOT = rbt_insert(RBT_ROOT, i)

    return ans


def debug_print(children, values, colors, counts, root):
    print(children.T)
    print(values)
    print(colors)
    print(counts)
    _debug_print(children, values, colors, counts, root, 0)


def _debug_print(children, values, colors, counts, i, depth):
    if i != -1:
        _debug_print(children, values, colors, counts, children[i, 0], depth + 1)
        print('      ' * depth, 'BR'[colors[i]], values[i], counts[i])
        _debug_print(children, values, colors, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)
    pass

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    class minseg():
        
        def __init__(self, arr):
            self.n = len(arr)
            self.ide_ele = arr[0]
            self.num =2**((self.n-1).bit_length())
            self.seg=[self.ide_ele]*2*self.num
            for i in range(self.n):
                self.seg[i+self.num-1]=arr[i]
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 

        def segfunc(self, x, y):
            return min(x, y)

            
        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
            
        def query(self, p, q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res

    class maxseg():
        
        def __init__(self, arr):
            self.n = len(arr)
            self.ide_ele = arr[0]
            self.num =2**((self.n-1).bit_length())
            self.seg=[self.ide_ele]*2*self.num
            for i in range(self.n):
                self.seg[i+self.num-1]=arr[i]
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 

        def segfunc(self, x, y):
            return max(x, y)

            
        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
            
        def query(self, p, q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res

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

    ind = {}
    for i in range(n):
        ind[a[i]] = i
    smax = maxseg([0]*n)
    smin = minseg([n+1]*n)

    res = 0
    for i in range(n):
        # 配列の1-indexed
        pos = ind[n-i] + 1

        l1 = smax.query(0, pos)
        l2 = smax.query(0, l1)
        r1 = smin.query(pos, n+2)
        r2 = smin.query(r1+1, n+2)
        res += ((l1-l2)*(r1-pos) + (r2-r1)*(pos-l1)) * (n-i)

        smin.update(pos, pos)
        smax.update(pos, pos)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:


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

order = [-1 for i in range(n+1)]
for i in range(n):
    order[data[i]]=i

sqn = int(math.sqrt(n)+1)



myLeft = [-1 for i in range(n)]
myRight = [n for i in range(n)]

list1 = [0 for i in range(sqn*sqn)]
list2 = [0 for i in range(sqn)]

for i in range(n,0,-1):
    ## add data
    list1[order[i]] = 1
    list2[order[i]//sqn] = 1
    
    ## find L
    #stage-1
    left = -1
    pos2 = order[i]//sqn
    pos1 = order[i] %sqn - 1
    
    while(pos1 >= 0):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            left = now
            break
        else:
            pos1 -= 1
            
    if(left >= 0):
        myLeft[order[i]] = left
        continue

    #stage-2
    pos2 -= 1
    while(pos2 >= 0):
        if(list2[pos2] == 1):
            break
        else:
            pos2-=1
    if(pos2<0):
        continue
    
    #stage-3
    pos1 = sqn-1
    while(pos1 >= 0):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            left = now
            break
        else:
            pos1 -= 1

    if(left >= 0):
        myLeft[order[i]] = left
        continue

print(list1,list2,myLeft)


list1 = [0 for i in range(sqn*sqn)]
list2 = [0 for i in range(sqn)]

for i in range(n,0,-1):
    ## add data
    list1[order[i]] = 1
    list2[order[i]//sqn] = 1
    
    ## find L
    #stage-1
    right = -1
    pos2 = order[i]//sqn
    pos1 = order[i] %sqn + 1
    
    while(pos1 < sqn):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            right = now
            break
        else:
            pos1 += 1
            
    if(right >= 0):
        myRight[order[i]] = right
        continue

    #stage-2
    pos2 += 1
    while(pos2 < sqn):
        if(list2[pos2] == 1):
            break
        else:
            pos2+=1
    if(pos2>=sqn):
        continue
    
    #stage-3
    pos1 = 0
    while(pos1 < sqn):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            right = now
            break
        else:
            pos1 += 1

    if(right >= 0):
        myRight[order[i]] = right
        continue

print(list1,list2,myRight)

ans = 0

for i in range(n):
    if(myLeft[i]!=-1):
        numLeft = myLeft[i] - myLeft[myLeft[i]]
        numRight = myRight[i] - i
        print(i,"L",numLeft,numRight)
        ans += data[i] * numLeft * numRight
    if(myRight[i]!=n):
        numLeft = i - myLeft[i]
        numRight = myRight[myRight[i]] - myRight[i]
        print(i,"R",numLeft,numRight)
        ans += data[i] * numLeft * numRight

print(ans)

Submission status: Runtime Error

Solution code:
for item in p_list:
    p_list1.append(int(item))
current_value = 0

for L in range(N - 1):
    
    for R in range(L + 1, N):
        if R == L + 1:
            first_value = max(p_list1[L], p_list1[R])
            second_value = min(p_list1[L], p_list1[R])
            
        else:
            if first_value < p_list1[R]:
                first_value = p_list1[R]
                second_value = first_value

            elif first_value >= p_list1[R] and second_value <= p_list1[R]:
                second_value = p_list1[R]

        

        current_value += second_value
        
print(current_value)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <cassert>
#include <random>


int main() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    std::vector<int> id(n);
    std::iota(id.begin(), id.end(), 0);
    std::sort(id.begin(), id.end(), [&](int i, int j) {
        return a[i] > a[j];
    });
    std::multiset<int> s;
    s.insert(-1); s.insert(-1);
    s.insert(n); s.insert(n);
    long long ans = 0;
    for (int i : id) {
        auto itr = s.lower_bound(i);
        long long r0 = *itr;
        itr++;
        long long r1 = *itr;
        itr--;
        itr--;
        long long l0 = *itr;
        itr--;
        long long l1 = *itr;
        ans += a[i]*(r1 - r0)*(i - l0);
        ans += a[i] * (l0 - l1)*(r0 - i);
        s.insert(i);
    }
    std::cout << ans << std::endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
n=int(input())
p=list(map(int,input.split()))
s=[0,0]
t=[n+1,n+1]
a=[]
for i in reversed(range(1,n)):
  if p.index(i)<p.index(i+1):
    t.append(p.index(i+1))
  elif p.index(i)>p.index(i+1):
    s.append(p.index(i+1))
  w=sorted(s)[-1]
  x=sorted(s)[-2]
  y=sorted(t)[0]
  z=sorted(t)[1]
  c=(w-x)*(y-p.index(i))+(p.index(i)-w)*(z-y)
  a.append(i*c)
print(sum(a))

Submission status: Runtime Error

Solution code:
n = int(input())
p = list(map(int,input().split()))
p_ind = [ (p[i], i+1) for i in range(n) ]
p_ind.sort(reverse=True)

import bisect
a = [0,0,n+1,n+1]
ans = 0
for tmp in p_ind:
    val, i = tmp
    j = bisect.bisect(a,i)
    ans += ((a[j+1] - a[j])* (i - a[j-1]) + (a[j] - i)* (a[j-1] - a[j-2])) * val
    a.insort(j,i)

print(ans)

Submission status: Runtime Error

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

    if N == 10 ** 5:
        appeared = []
        appeared.append(-1)
        appeared.append(pindex[N - 1])
        appeared.append(N)
    
        total = 0
        for i in reversed(range(N - 1)):
            mid = bisect(appeared, pindex[i])
            if pindex[i] == 0:
                total += i * (appeared[2] - appeared[1])
            elif pindex[i] == N - 1:
                total += i * (appeared[N - i] - appeared[N - i - 1])
            else:
                if mid == 1: total += i * (appeared[2] - appeared[1]) * (pindex[i] + 1)
                elif mid == N + 1 - i: total += i * (appeared[mid - 1] - appeared[mid - 2]) * (N - pindex[i])
                else: 
                    total += i * ((appeared[mid - 1] - appeared[mid - 2]) * (appeared[mid] - pindex[i]))
                    total += i * ((pindex[i] - appeared[mid-1]) * (appeared[mid+1] - appeared[mid]))
            appeared.insert(mid, pindex[i])
 
        print(total)

    else:
        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: Runtime Error

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
    if N == 10 ** 5:
        appeared = []
        appeared.append(-1)
        appeared.append(pindex[N])
        appeared.append(N)
    
        total = 0
        for i in reversed(range(1, N)):
            mid = bisect(appeared, pindex[i])
            if pindex[i] == 0:
                total += i * (appeared[2] - appeared[1])
            elif pindex[i] == N - 1:
                total += i * (appeared[N - i] - appeared[N - i - 1])
            else:
                if mid == 1: total += i * (appeared[2] - appeared[1]) * (pindex[i] + 1)
                elif mid == N + 1 - i: total += i * (appeared[mid - 1] - appeared[mid - 2]) * (N - pindex[i])
                else: 
                    total += i * ((appeared[mid - 1] - appeared[mid - 2]) * (appeared[mid] - pindex[i]))
                    total += i * ((pindex[i] - appeared[mid-1]) * (appeared[mid+1] - appeared[mid]))
            appeared.insert(mid, pindex[i])
 
        print(total)
        
    else:
        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: Runtime Error

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, key):
        self.root = Node(key, 1) #根
        self.change = True #修正フラグ

    ###############
    #回転操作, 修正操作
    ###############
    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 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(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()