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:
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12_rec(i, j, segi):
        if j - i <= 0:
            return (0, 0)
        seg = segt[segi]
        if j - i == 1:
            return seg[i]
        arr = []
        if i % 2 == 1:
            a, b = seg[i]
            arr.append(a)
            arr.append(b)
            i += 1
        if j % 2 == 1:
            a, b = seg[j - 1]
            arr.append(a)
            arr.append(b)
            j -= 1
        a, b = get12_rec(i // 2, j // 2, segi + 1)
        arr.append(a)
        arr.append(b)
        arr.sort()
        return arr[-1], arr[-2]

    def get12(i, j):
        return get12_rec(i, j, 0)

    cache = {}

    def rec(i, j):
        if j - i < 2:
            return 0
        if (i, j) in cache:
            return cache[(i, j)]

        #dprint('i j', i, j)
        a, b = get12(i, j)
        #dprint('a b', a, b)
        ai = revp[a]
        bi = revp[b]
        assert i <= ai < j
        assert i <= bi < j
        li, ri = (ai, bi) if ai < bi else (bi, ai)
        ri += 1
        #dprint('li ri', li, ri)

        mid = rec(li + 1, ri - 1)
        left = rec(i, ri - 1)
        right = rec(li + 1, j)

        #dprint('i j mid left right', i, j, mid, left, right)
        #dprint('b li ri score', b, li, ri,
        #       b * (li - i + 1) * (j - ri + 1))
        v = left + right - mid + b * (li - i + 1) * (j - ri + 1)
        cache[(i, j)] = v
        return v

    return rec(0, N)


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
P=list(map(int,input().split()))
I=[0]*N
for i,p in enumerate(P):
    I[N-p]=i
import sys
sys.setrecursionlimit(10**5)
class BIT:
    def __init__(self,size):
        self.N=size
        self.v=[0]*(self.N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.v[i]+=x
            i+=i&-i
    def sum(self,a,b=0):
        if a>b:
            a,b=b,a
        if a>0:
            r=self.sum(b)-self.sum(a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.v[i]
                i-=i&-i
        return r
    def right(self,x):
        a,b=x+1,self.N
        while a+1<b:
            t=(a+b)//2
            if self.sum(a,t)>0:
                b=t
            else:
                a=t
        return a 
    def left(self,x):
        a,b=0,x
        while a+1<b:
            t=(a+b)//2
            if self.sum(t,b)>0:
                a=t
            else:
                b=t
        return a
b=BIT(2**14)
b.add(0,N+1)
b.add(1,N+1)
b.add(N+2,N+1)
b.add(N+3,N+1)
a=0
p=N
for i in I:
    l=b.left(i+2)
    ll=b.left(l)
    r=b.right(i+2)
    rr=b.right(r)
    if 1<l and r<N+2:
        a+=((l-ll)*(r-i-2)+(rr-r)*(i+2-l))*p
    elif 1<l:
        a+=(l-ll)*(N-i)*p
    elif r<N+2:
        a+=(rr-r)*(i+1)*p
    b.add(i+2,p)
    p-=1
print(a)

Submission status: Runtime Error

Solution code:
N=int(input())
P=list(map(int,input().split()))
I=[0]*N
for i,p in enumerate(P):
    I[N-p]=i
class BIT:
    def __init__(self,size):
        self.N=size
        self.v=[0]*(self.N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.v[i]+=x
            i+=i&-i
    def sum(self,a,b=0):
        if a>b:
            a,b=b,a
        if a>0:
            r=self.sum(b)-self.sum(a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.v[i]
                i-=i&-i
        return r
    def right(self,x):
        a,b=x+1,self.N
        while a+1<b:
            t=(a+b)//2
            if self.sum(a,t)>0:
                b=t
            else:
                a=t
        return a 
    def left(self,x):
        a,b=0,x
        while a+1<b:
            t=(a+b)//2
            if self.sum(t,b)>0:
                a=t
            else:
                b=t
        return a
b=BIT(2**14)
b.add(0,N+1)
b.add(1,N+1)
b.add(N+2,N+1)
b.add(N+3,N+1)
a=0
p=N
for i in I:
    l=b.left(i+2)
    ll=b.left(l)
    r=b.right(i+2)
    rr=b.right(r)
    if 1<l and r<N+2:
        a+=((l-ll)*(r-i-2)+(rr-r)*(i+2-l))*p
    elif 1<l:
        a+=(l-ll)*(N-i)*p
    elif r<N+2:
        a+=(rr-r)*(i+1)*p
    b.add(i+2,p)
    p-=1
print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
P = list(map(int, input().split()))

sum_result = 0
for L in range(N - 1):
  if P[L] > P[L+1]:
    first, second = P[L : L+2]
  else:
    second, first = P[L : L+2]
  sum_result += second
  for R in range(L + 2 : N):
    if P[R] > first:
      second = first
      first = P[R]
    elif P[R] > second:
      second = P[R]
    sum_result += second
print(sum_result)

Submission status: Runtime Error

Solution code:
n = int(input())
P = list([int(x) for x in input().split()])
PP_i = sorted(range(len(P)), key=lambda k: P[k], reverse=True)
S = {0, n+1}
T = list(i for i in range(n+2))
ans = 0

for i in P_i:
    S1 = T[0:i+1]
    l1 = sorted(S.intersection(S1))[-1]
    if l1 == 0:
        l2 = 0
    else:
        l2 = sorted(S.intersection(S1))[-2]
    h1 = sorted(S.difference(S1))[0]
    if h1 == n+1:
        h2 = n+1
    else:
        h2 = sorted(S.difference(S1))[1]
    ans += P[i] * ((l1-l2)*(h1-(i+1)) + (i+1-l1)*(h2-h1))
    S.add(i+1)

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") 
  
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;

int n, e[(int)1e5 + 5];

int main()
{
    cin >> n;
    
    for(int i = 1; i <= n; ++ i)
    {
        int u; 
        
        cin >> u;
        
        e[u] = i;
    }
    
    ll res = 0;
    
    multiset < int > w;
    
    w.insert(0);
    w.insert(0);
    w.insert(n + 1);
    w.insert(n + 1);
    
    for(int i = n; i >= 1; --i)
    {
        ll a = i;
        
        w.insert(e[a]);
        
        auto z = w.find(e[a]), x = prev(z), c = prev(x), v = next(z), b = next(v);
        
        int s = *x, d = *c, f = *v, g = * b;
        
        
        ll ans = (f - e[i]) * 1LL * (s - d) + 1LL * (g - f) * (e[i] - s);
        
        res += ans * a;
    }
    
    cout << res << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") 
  
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;

int n, q[(int)1e5 + 5];

int main()
{
    cin >> n;
    
    for(int i = 1; i <= n; ++ i)
    {
        int u; 
        
        cin >> u;
        
        q[u] = i;
    }
    
    ll res = 0;
    
    multiset < int > w;
    
    w.insert(0);
    w.insert(0);
    w.insert(n + 1);
    w.insert(n + 1);
    
    for(int i = n; i >= 1; --i)
    {
        ll a = i;
        
        w.insert(q[a]);
        
        auto z = w.find(q[a]), x = prev(z), c = prev(x), v = next(z), b = next(v);
        
        int nx = *x, nc = *c, nv = *v, nb = * b;
        
        
        ll ans = (nv - q[i]) * 1LL * (nx - nc) + 1LL * (nb - nv) * (q[i] - nx);
        
        res += ans * a;
    }
    
    cout << res << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
N = int(input())
P = list(map(int, input().split()))
 
left_bigger  = [0] + [i for i in range(N+1)]
right_bigger = [i+1 for i in range(N+1)] + [N+1]
 
E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v,i in E:
    l0=left_bigger[i]
    l1=left_bigger[l0]
    r0=right_bigger[i]
    r1=right_bigger[r0]
    print(left_bigger)
    ans += ((r1-r0)*(i-l0) + (r0-i)*(l0-l1))*v
    left_bigger[r0]=l0
    right_bigger[l0]=r0
print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<set>

using namespace std;

int N;
int main() {
    cin >> N;

    int P[N];
    int value_index[N+1];
    for(int i = 0; i < N; i++) {
        cin >> P[i];
        value_index[P[i]] = i;
    }

    auto cmp = [](int a, int b) { return a > b;};

    set<int> larger_idx_right;
    set<int, decltype(cmp)> larger_idx_left(cmp);
    larger_idx_right.insert(value_index[N]);
    larger_idx_left.insert(value_index[N]);

    set<int>::iterator it;

    int ans = 0;

    for(int i = N-1; i > 0; i--) {
        int right_1 = N;
        int right_2 = N;
        it = larger_idx_right.upper_bound(value_index[i]);
        if(it != larger_idx_right.end()) {
            right_1 = *it;
            it = larger_idx_right.upper_bound(right_1);
            if(it != larger_idx_right.end()) {
                right_2 = *it;
            }
        } 

        int left_1 = -1;
        int left_2 = -1;
        it = larger_idx_left.upper_bound(value_index[i]);
        if(it != larger_idx_left.end()) {
            left_1 = *it;
            it = larger_idx_left.upper_bound(left_1);
            if(it != larger_idx_left.end()) {
                left_2 = *it;
            }
        } 

        larger_idx_right.insert(value_index[i]);
        larger_idx_left.insert(value_index[i]);

//        cout << i << " " << left_2 << " " << left_1 << " " << right_1 << " " << right_2 << endl;

        if (right_1 != N) {
            int con = i*(value_index[i]-left_1)*(right_2-right_1);
//            cout << "con right_1 " << con << endl;
            ans += con;
        }
        if (left_1 != -1) {
            int con = i*(right_1-value_index[i])*(left_1-left_2);
//            cout << "cont left 1 " << con << endl;
            ans += con;
        }
    }

    cout << ans << endl;
}

Submission status: Runtime Error

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


import queue
from collections import deque




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

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

    ind_list = deque([0, 0, num + 1, num + 1])
    # ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        # bisect.insort_left(ind_list, ori_ind)
        # add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = -1
        ind_list.insert(add_ind, ori_ind)
        # print(add_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import time


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

# key 未満の最大値
    def search_lower(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] < key:
                ret = self.key[idx]
                idx = self.right[idx]
            else:
                idx = self.left[idx]
        return ret

# key 超過の最小値
    def search_higher(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] > key:
                ret = self.key[idx]
                idx = self.left[idx]
            else:
                idx = self.right[idx]
        return ret

# 要素の挿入
# 重複を考慮しない
# ToDo: 考慮するものも実装する
    def insert(self, key):
        self.last_index += 1
        self.key[self.last_index] = key
        self.weight[self.last_index] = 2
        self.root = self.__recursive_insert__(self.root)
        NotImplemented

# insert の再帰実装に用いる
    def __recursive_insert__(self, idx):
        if idx == 0:
            return self.last_index
        elif self.key[self.last_index] < self.key[idx]:
            self.left[idx] = self.__recursive_insert__(self.left[idx])
            self.__fix__(idx)
            return self.__fix_left_bias__(idx)
        else:
            self.right[idx] = self.__recursive_insert__(self.right[idx])
            self.__fix__(idx)
            return self.__fix_right_bias__(idx)

# ノードの weight を補正する
    def __fix__(self, idx):
        self.weight[idx] = self.weight[self.left[idx]] + \
            self.weight[self.right[idx]]

# 左回転
    def __rotate_left__(self, idx):
        right = self.right[idx]
        self.right[idx] = self.left[right]
        self.__fix__(idx)
        self.left[right] = idx
        self.__fix__(right)
        return right

# 右回転
    def __rotate_right__(self, idx):
        left = self.left[idx]
        self.left[idx] = self.right[left]
        self.__fix__(idx)
        self.right[left] = idx
        self.__fix__(left)
        return left

# 左偏状態の補正
    def __fix_left_bias__(self, idx):
        if self.weight[self.right[idx]] * 4 < self.weight[idx]:
            left = self.left[idx]
            if self.weight[self.left[left]] * 4 < self.weight[left]:
                self.left[idx] = self.__rotate_left__(left)
            idx = self.__rotate_right__(idx)
        return idx

# 右偏状態の補正
    def __fix_right_bias__(self, idx):
        if self.weight[self.left[idx]] * 4 < self.weight[idx]:
            right = self.right[idx]
            if self.weight[self.right[right]] * 4 < self.weight[right]:
                self.right[idx] = self.__rotate_right__(right)
            idx = self.__rotate_left__(idx)
        return idx

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

    def deb_print(self):
        self.__deb_print__(self.root, 0)

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


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    #print(idx)
    t = WeightBalancedTree(10)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        #print("")
        #print("")
        #print("begin tree")
        #t.deb_print()
        #print("end tree")
        #print('now size = {0}'.format(t.size()))
        #print('now i = {0}'.format(i))
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        #print([prepre, pre, nex, nexnex])
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
from random import shuffle
import cProfile
sys.setrecursionlimit(200000)
# local only
if not __debug__:
    fin = open('text.txt', 'r')
    sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class Avltree:
    """
    AVL木

    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """

    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"

    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node  # node.key == keyの場合
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None

    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans

    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans


    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key

    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.key


    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self  # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self, p, v):  # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else:
            p.right = v
    def insert(self, key):  # rootでのみ呼ばれる挿入
        if self.key is None:  # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self, key)
        else:  # key == self.key:
            pass  # do not overwrite
    def insertx(self, p, key):  # replaceを呼ぶために一つ上の親を持っているinsert
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    break
                else:
                    node = node.right
        while len(s) != 0:
            p, direct = s.pop()
            if node == p:
                continue
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(p, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(p, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(p, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(p, node.SingleLeftRotation())
                    break
            node = p

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key

def bin_tree_to_list(root):
    """
    type root: root class
    """
    if not root:
        return root
    root = bin_tree_to_list_util(root)
    while root.left:
        root = root.left
    return root

def bin_tree_to_list_util(root):
    if not root:
        return root
    if root.left:
        left = bin_tree_to_list_util(root.left)
        while left.right:
            left = left.right
        left.right = root
        root.left = left
    if root.right:
        right = bin_tree_to_list_util(root.right)
        while right.left:
            right = right.left
        right.left = root
        root.right = right
    return root

def print_tree(root):
    while root:
        print(root.key)
        root = root.right

def binary_tree_paths(root):
    res = []
    if root is None:
        return res
    dfs(res, root, str(root.key))
    return res

def dfs(res, root, cur):
    if root.left is None and root.right is None:
        res.append(cur)
    if root.left:
        dfs(res, root.left, cur + '->' + str(root.left.key))
    if root.right:
        dfs(res, root.right, cur + '->' + str(root.right.key))
# END CUT HERE



def main():
    N = ii()
    P = lmi()
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    # debug(L)
    ans = 0
    rb = Avltree()
    for num, i in enumerate(L):
        rb.insert(i)
        l1 = rb.search_lower(i, -1)
        l2 = rb.search_lower(l1, -1)
        r1 = rb.search_higher(i, N)
        r2 = rb.search_higher(r1, N)
        # debug(l2, l1, r1, r2)
        ans += (abs(i - l1) * abs(r2 - r1) + abs(l1 - l2) * abs(r1 - i)) * (N - num)
    print(ans)
    # print(rb.inorder())
    # N = 100000
    # a = [i for i in range(N)]
    # with open('text.txt', 'w') as f:
    #     print(N, file=f)
    #     print(*a, file=f)
    return



if __name__ == '__main__':
    # cProfile.run('main()')
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
P = [ int(n) for n in input().split() ]

I = np.argsort(P)[::-1]

w = [ -1 for _ in range(N)]
x = [ -1 for _ in range(N)]
y = [ N  for _ in range(N)]
z = [ N  for _ in range(N)]
    
for j in range(N):
    p = I[j]
    for q in range(w[p]+1, x[p]):
        z[q] = p
    for q in range(x[p]+1, p):
        z[q] = y[q]
        y[q] = p
    for q in range(p+1, y[p]):
        w[q] = x[q]
        x[q] = p
    for q in range(y[p]+1, z[p]):
        w[q] = p

s = 0
for i in range(N):
    s += P[i] * ( (x[i]-w[i])*(y[i]-i) + (i-x[i])*(z[i]-y[i]) )
    # w[i] < L <= x[i] and    i <= R < y[i]
    # or
    # x[i] < L <= i    and y[i] <= R < z[i]
        
print(s)

Submission status: Runtime Error

Solution code:
# E - Second Sum
import numpy as np
N = int(input())
B = np.array(list(map(int, input().split())))

dp = np.array([np.zeros(N - 1)] * (N - 1))

for i in range(N - 1):
    first = max(B[i], B[i + 1])
    second = min(B[i], B[i + 1])
    dp[i][i] = second
    if i > 0:
        for j in range(i):
            tmp = B[i - j - 1]
            if tmp >= first:
                second = first
                first = tmp
            elif tmp >= second:
                second = tmp
            dp[i - j - 1][i] = second

print(dp.sum())

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))[::-1]



result=0

for i range(n-1):
  maxV=max(a[i],a[i+1])
  temp=min(a[i],a[i+1])
  result+=temp
  for j in range(i+2,n):
    if temp>a[j]:
      result+=temp
      #print(i,j)
    else:
      if a[j]>maxV:
        temp=maxV
        result+=temp
        maxV=a[j]
      else:
        temp=a[j]
        result+=temp
    #print(i,j,temp)
        

  

  
print(result)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))[::-1]


i=0
result=0

for i range(n-1):
  maxV=max(a[i],a[i+1])
  temp=min(a[i],a[i+1])
  result+=temp
  j=i+2
  for j in range(i+2,n):
    if temp>a[j]:
      result+=temp
      #print(i,j)
    else:
      if a[j]>maxV:
        temp=maxV
        result+=temp
        maxV=a[j]
      else:
        temp=a[j]
        result+=temp
    #print(i,j,temp)
        

  

  
print(result)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))[::-1]


i=0
result=0

for i range(n-1):
  maxV=max(a[i],a[i+1])
  temp=min(a[i],a[i+1])
  result+=temp
  j=i+2
  for j in range(i+2,j):
    if temp>a[j]:
      result+=temp
      #print(i,j)
    else:
      if a[j]>maxV:
        temp=maxV
        result+=temp
        maxV=a[j]
      else:
        temp=a[j]
        result+=temp
    #print(i,j,temp)
        

  

  
print(result)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))[::-1]


i=0
result=0

for i range(n-1):
  maxV=max(a[i],a[i+1])
  temp=min(a[i],a[i+1])
  result+=temp
  j=i+2
  for j in range(i+2,j)
    if temp>a[j]:
      result+=temp
      #print(i,j)
    else:
      if a[j]>maxV:
        temp=maxV
        result+=temp
        maxV=a[j]
      else:
        temp=a[j]
        result+=temp
    #print(i,j,temp)
        

  

  
print(result)