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:
#incited from https://juppy.hatenablog.com/entry/2019/02/26/python_AVL%E6%9C%A8_%E9%85%8D%E5%88%97ver_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_
#AVL Tree code by juppy

#AVL

##search(0,x):O(logN)
# xがある場合indexを、ない場合Noneを返す
def search(root,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return None
        else:
            return search(avl_left[root],key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return None
        else:
            return search(avl_right[root],key)
    return root


##end_lower/higher:search_lower/higherで使用
def end_lower(root):
    if avl_left[root] == None:
        return avl_key[root]
    else:
        return end_lower(avl_left[root])

def end_higher(root):
    if avl_right[root] == None:
        return avl_key[root]
    else:
        return end_higher(avl_right[root])


##search_lower(0,x,None):O(logN)
# xより小さいものの中で最も大きいものを出力。ない場合はNoneを出力
def search_lower(root,key,lower_key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return lower_key
        else:
            return search_lower(avl_left[root],key,lower_key)
    if avl_key[root] < key:
        lower_key = avl_key[root]
        if avl_right[root] == None:
            return lower_key
        else:
            return search_lower(avl_right[root],key,lower_key)
    
    # == 
    if avl_left[root] == None:
        return lower_key
    else:
        if lower_key == None:
            return end_higher(avl_left[root])
        else:
            return max(lower_key,end_higher(avl_left[root]))

##search_higher(0,x,None):O(logN)
# xより大きいものの中で最も小さいものを出力。ない場合はNoneを出力
def search_higher(root,key,higher_key):
    if avl_key[root] > key:
        higher_key = avl_key[root]
        if avl_left[root] == None:
            return higher_key
        else:
            return search_higher(avl_left[root],key,higher_key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return higher_key
        else:
            return search_higher(avl_right[root],key,higher_key)
    
    # == 
    if avl_right[root] == None:
        return higher_key
    else:
        if higher_key == None:
            return end_lower(avl_right[root])
        else:
            return min(higher_key,end_lower(avl_right[root]))



##Rotation,replace,insertx:insertで使用
def DoubleRightRotation(x):
    tl = avl_left[x]
    avl_left[x] = avl_right[avl_right[tl]]
    avl_right[avl_right[tl]] = x
    tlr = avl_right[tl]
    avl_right[tl] = avl_left[tlr]
    avl_left[tlr] = tl
    if balance[tlr] == -1:
        balance[avl_right[tlr]] = 1
        balance[avl_left[tlr]] = 0
    elif balance[tlr] == 1:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = -1
    else:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = 0
    balance[tlr] = 0
    return tlr

def DoubleLeftRotation(x):
    tr = avl_right[x]
    avl_right[x] = avl_left[avl_left[tr]]
    avl_left[avl_left[tr]] = x
    trl = avl_left[tr]
    avl_left[tr] = avl_right[trl]
    avl_right[trl] = tr
    if balance[trl] == 1:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = -1
    elif balance[trl] == -1:
        balance[avl_left[trl]] = 0
        balance[avl_right[trl]] = 1
    else:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = 0
    balance[trl] = 0
    return trl

def SingleLeftRotation(x):
    tr = avl_right[x]
    balance[tr] = 0
    balance[x] = 0
    avl_right[x] = avl_left[tr]
    avl_left[tr] = x
    return tr

def SingleRightRotation(x):
    tl = avl_left[x]
    balance[tl] = 0
    balance[x] = 0
    avl_left[x] = avl_right[tl]
    avl_right[tl] = x
    return tl

def replace(x,p,v):
    if avl_left[p] == x:
        avl_left[p] = v
    else:
        avl_right[p] = v

def insertx(root,p,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            if not insertx(avl_left[root],root,key):
                return False
        if balance[root] == 1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = -1
            return True
        else:
            if balance[avl_left[root]] == 1:
                replace(root,p,DoubleRightRotation(root))
            elif balance[avl_left[root]] == -1:
                replace(root,p,SingleRightRotation(root))
            return False
    if avl_key[root] < key:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            if not insertx(avl_right[root],root,key):
                return False
        if balance[root] == -1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = 1
            return True
        else:
            if balance[avl_right[root]] == -1:
                replace(root,p,DoubleLeftRotation(root))
            elif balance[avl_right[root]] == 1:
                replace(root,p,SingleLeftRotation(root))
            return False
    return False


##insert(0,x):O(logN)
#x追加
def insert(root,key):
    if key < avl_key[root]:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            insertx(avl_left[root],root,key)
    elif key > avl_key[root]:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            insertx(avl_right[root],root,key)
    else:
        pass

n=int(input())
arr=list(map(int,input().split()))
arr2=[[arr[i],i+1] for i in range(n)]
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
avl_key=[0]
avl_left=[None]*(n+2)
avl_right=[None]*(n+2)
balance=[0]*(n+2)
ans=0
insert(0,n+1)
for i in range(n):
  val,pos=arr2[i]
  fl=search_lower(0,pos,None)
  if fl==0:
    sl=0
  else:
    sl=search_lower(0,fl,None)
  fr=search_higher(0,pos,None)
  if fr==n+1:
    sr=n+1
  else:
    sr=search_higher(0,fr,None)
  cnt=(fl-sl)*(fr-pos)+(pos-fl)*(sr-fr)
  ans+=cnt*val
  print(sl,fl,pos,fr,sr,cnt,val,tmp)
  insert(0,pos)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import bisect
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
# template


def solve():
    n=int(readline())
    p = list(map(int, readline().split()))
    #print(p)
    idx=[0]*(n)
    for i in range(n):
        idx[p[i]-1]=i
    perm=deque([-1,idx[-1],n])
    #print(perm)
    count=0
    for i in range(n-2,-1,-1):
        id=bisect.bisect_left(perm,idx[i])
        if id!=1:
            count+=(i+1)*((perm[id-1]-perm[id-2])*(perm[id]-idx[i]))
        if id!=n-i:
            count+=(i+1)*((perm[id+1]-perm[id])*(idx[i]-perm[id-1]))
        perm.insert(id,idx[i])
    print(count)
    return


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import bisect
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
# template


def solve():
    n=int(readline())
    p = tuple(map(int, readline().split()))
    #print(p)
    idx=[0]*(n)
    for i in range(n):
        idx[p[i]-1]=i
    perm=deque([-1,idx[-1],n])
    #print(perm)
    count=0
    for i in range(n-2,-1,-1):
        id=bisect.bisect_left(perm,idx[i])
        if id!=1:
            count+=(i+1)*((perm[id-1]-perm[id-2])*(perm[id]-idx[i]))
        if id!=n-i:
            count+=(i+1)*((perm[id+1]-perm[id])*(idx[i]-perm[id-1]))
        perm.insert(id,idx[i])
    print(count)
    return


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))

    class segtree():
        def __init__(self,base,monoid,ini):#self,モノイド,元の配列
            #ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
            #basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
            
            # 初期値（上限とか下限）を決定
            self.ini=ini
            #セグ木の要素数（num）および深さ（depth）を計算
            self.base=base
            self.basesize=len(self.base)
            self.num,self.depth=1,1
            while self.num<self.basesize:
                self.num*=2
                self.depth+=1
            self.num-=1
            #関数（モノイド、今回はmin）を設定
            self.monoid=monoid
            #セグ木を構築
            self.treesize=self.num+self.basesize
            self.tree=[None]*self.treesize
            #segtree[m]以降に代入したい配列を入力していく
            for i in range(self.num, self.treesize):self.tree[i]=self.base[i-self.num]
            #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(self.num-1,-1,-1):
                j=2*i+1
                if j>=self.treesize:self.tree[i]=self.ini
                else:self.tree[i]=self.monoid(self.tree[j],self.tree[min(j+1,self.treesize-1)])
        
        #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
        def max_index(self,index_func):
            #探していく
            i=0
            while i<self.num:
                k=2*i+1
                if k+1<self.treesize:
                    if index_func(self.tree[k+1]):
                        i=k+1
                        continue
                if k<self.treesize:
                    if index_func(self.tree[k]):
                        i=k
                        continue
                return -1
            return i-self.num
    
        #条件を満たす(サンプルの条件はs以下になること)最小のインデックスを返す関数
        def min_index(self,index_func):
            #探していく
            i=0
            while i<self.num:
                k=2*i+1
                if k<self.treesize:
                    if index_func(self.tree[k]):
                        i=k
                        continue
                if k+1<self.treesize:
                    if index_func(self.tree[k+1]):
                        i=k+1
                        continue
                return -1
            return i-self.num
    
        #半開区間[lower,upper)の最小値（とか）を探す関数
        def search(self,lower, upper):
            q=[[0,1]]  #インデックス、階層
            #返り値を初期化
            ret=self.ini
            while q:
                i,f=q.pop()
                #popしたインデックスと階層から、求める下限と上限を算出する
                #幅
                width=pow(2,self.depth-f)
                #下限と中央と上限
                kagen=(i-pow(2,f-1)+1)*width
                chuo=kagen+width//2
                jogen=kagen+width
                k=2*i+1
                if lower<=kagen and jogen<=upper:
                    ret=self.monoid(ret,self.tree[i])
                    continue
                if k<self.treesize:
                    if lower<=kagen and chuo<=upper:ret=self.monoid(ret,self.tree[k])
                    elif lower<=chuo:q.append([k,f+1])
                if k+1<self.treesize:
                    if lower<=chuo and jogen<=upper:ret=self.monoid(ret,self.tree[k+1])
                    elif chuo<=upper:q.append([k+1,f+1])
            return ret
    
        #base[i]をsに更新したときにセグ木全体を更新する関数
        def update(self,index,new_value):
            i=index+self.num
            self.tree[i]=new_value
            temp=new_value
            while i!=0:
                k=(i-1)//2
                if i%2==1:
                    temp=self.monoid(self.tree[min(i+1,self.treesize-1)],temp)
                else:
                    temp=self.monoid(self.tree[i-1],temp)
                if self.tree[k]!=temp:
                    self.tree[k]=temp
                    i=k
                    continue
                break
    
    s=segtree([10**6,10**6]+a+[10**6+10**6],max,0)

    d=[0]*n
    for i in range(n):
        d[a[i]-1]=i
    ans=0
    for i in range(1,n):
        j=d[i-1]
        aa=j+3
        b=n+3
        ini=aa
        while True:
            med=(aa+b)//2
            if aa==b:return aa
            if aa+1==b:
                if s.search(ini,aa+1)>i:
                    k1=aa
                    break
                else:
                    k1=b
                    break
            elif s.search(ini,med+1)>i:b=med
            else:aa=med+1
        aa=k1+1
        b=n+4
        ini=aa
        while True:
            med=(aa+b)//2
            if aa==b:return aa
            if aa+1==b:
                if s.search(ini,aa+1)>i:
                    cnt1=min(aa,n+2)-k1
                    break
                else:
                    cnt1=min(b,n+2)-k1
                    break
            elif s.search(ini,med+1)>i:b=med
            else:aa=med+1
        aa=1
        b=j+1
        ini=b
        while True:
            med=(aa+b)//2
            if aa==b:
                k2=aa
                break
            elif aa+1==b:
                if s.search(b,ini+1)>i:
                    k2=b
                    break
                else:
                    k2=aa
                    break
            elif s.search(med,ini+1)>i:aa=med
            else:b=med-1
        aa=0
        b=k2-1
        ini=b
        while True:
            med=(aa+b)//2
            if aa==b:
                k2=aa
                break
            elif aa+1==b:
                if s.search(b,ini+1)>i:
                    cnt2=k2-max(b,1)
                    break
                else:
                    cnt2=k2-max(aa,1)
                    break
            elif s.search(med,ini+1)>i:aa=med
            else:b=med-1
        ans+=(cnt2*(k1-j-2)+cnt1*(j-k2+2))*i
    print(ans)
main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  1 16:36:01 2019

@author: USER
"""

N=int(input())
P=list(map(int,input().split()))
for l in range (N-1):
    A=0
    for r in range(l+1,N):
        L=[]
        for w in range(l,r+1):
            L.append(P[w])
        a=max(L)
        d=[]
        for W in range(l,r+1):
            if P[W]>=a:
                d.append(0)
            else:
                d.append(P[W])
        a=max(d)
        A=A+a
    B=B+A
print(B)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  1 16:36:01 2019

@author: USER
"""

N=int(input())
P=[]
B=0
for i in range(N):
    p=int(input())
    P.append(p)
for l in range (N-1):
    A=0
    for r in range(l+1,N):
        L=[]
        for w in range(l,r+1):
            L.append(P[w])
        a=max(L)
        d=[]
        for W in range(l,r+1):
            if P[W]>=a:
                d.append(0)
            else:
                d.append(P[W])
        a=max(d)
        A=A+a
    B=B+A
print(B)

Submission status: Runtime Error

Solution code:
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector") 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>


#define ll long long
#define ull unsigned long long
#define int ll
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define ret(a) {cout << a; exit(0);}

using namespace std;

mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

typedef pair < int , int > pii ;
typedef pair < long long  , long long > pll ;

const int N = 1e5 + 1 , LOG = 18;
int n ;
int a[N], up[N] , sp[LOG][N];
int get(int l , int r){
	int x = up[r - l + 1];
//	cout << l << ' ' << r << ' ' << max(sp[x][l] , sp[x][r - (1 << x) + 1]) << '\n';
	//0 
	return max(sp[x][l] , sp[x][r - (1 << x) + 1]);
}
main(){
	cin >> n;
	up[0] = -1;
	for(int i = 1;  i <= n; i++){
		up[i] = up[i / 2] + 1;
    	cin >> a[i];
		sp[0][i] = a[i];
	}	
	for(int j = 1 ; j < LOG; j++)
		for(int i = 1 ; i + (1 << j) - 1<= n; i++)
			sp[j][i] = max(sp[j - 1][i] , sp[j - 1][i + (1 << j - 1)]);
	ll ans = 0;
	for(int i = 1 ; i <= n; i++){
		if(a[i] == n)
			continue;
		int L = 0, R = 0;
		{
			int l = 1 , r = i;
			while(l <= r){
			 	int m = (l + r) >> 1;
			 	if(get(m,i) == a[i])
			 		L = m , r = m - 1;
			 	else l = m + 1;
			}
		}
		{
			int l = i , r = n;
			while(l <= r){
				int m = (l + r) >> 1;
				if(get(i , m) == a[i])	
					R = m , l = m + 1;
				else r = m - 1;
			}
		}

        if(get(1,i) > a[i]){
			int Mx = 0, MxL = 0;
			int l = 1 , r = i - 1;
			while(l <= r){
				int m = (l + r) >> 1;
				if(get(m , i) > a[i])
					Mx = m , l = m + 1;
				else r = m - 1;	
			}
			l = 1 , r = Mx - 1 , MxL = Mx;
			while(l <= r){
				int m = (l + r) >> 1;
				if(get(m , Mx - 1) < a[i])
					MxL = m , r = m - 1;
				else l = m + 1;
			}
			ans += a[i] * (Mx - MxL + 1) * (R - i + 1);
		}
		if(get(i,n) > a[i]){
			int Mx = 0, MxR = 0;
			int l = i + 1 , r = n;
			while(l <= r){
				int m = (l + r) >> 1;
				if(get(i , m) > a[i])
					Mx = m , r = m - 1;
				else l = m + 1;	
			}
			l = Mx + 1 , r = n , MxR = Mx;
			while(l <= r){
				int m = (l + r) >> 1;
				if(get(Mx + 1 , m) < a[i])
					MxR = m , l = m + 1;
				else r = m - 1;
			}
			ans += a[i] * (MxR - Mx + 1) * (i - L + 1);			
		}

	}		
	cout << ans;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

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

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

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

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

# E
# 解説AC
# Piが何個使えるかというとこまでは良くて
# そのPiよりも大きい数字が左に2個右に2個必要というところまではいけた
# 問題の本質を解決できてはいない
# ここから解説
# 大きい順からみて見たものに対してインデックスを保持
# ここからbisectを使えばlogNでi付近のすでに追加したインデックスを持ってこれる
# あと少しだけどその少しが遠い
# ↑
# これは嘘
# BITを使え
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

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

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

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

    def __len__(self):
        return self.size

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

    print(ans)
    return

#F
def F():
    return


#Solve
if __name__ == '__main__':
    E()

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = list(map(int, input().split()))
first = np.zeros((n+1, n+2), dtype=int)
second = np.zeros((n+1, n+2), dtype=int)
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[l][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
ans = int(np.sum(second[1:, 1:]))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = tuple(map(int, input().split()))
first = np.zeros((n+1, n+2), dtype=int)
second = np.zeros((n+1, n+2), dtype=int)
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[l][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
ans = int(np.sum(second[1:, 1:]))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = tuple(map(int, input().split()))
first = np.zeros((n+1, n+2), dtype=int)
second = np.zeros((n+1, n+2), dtype=int)
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[l][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
ans = int(np.sum(second))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = tuple(map(int, input().split()))
first = np.zeros((n, n+1), dtype=int)
second = np.zeros((n, n+1), dtype=int)
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[l][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
ans = int(np.sum(second))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = tuple(map(int, input().split()))

first = np.zeros((n, n+1), dtype=int)
second = np.zeros((n, n+1), dtype=int)
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[l][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
print(int(np.sum(second)))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = tuple(map(int, input().split()))

first = np.zeros((n, n+1))
second = np.zeros((n, n+1))
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[l][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
print(int(np.sum(second)))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = tuple(map(int, input().split()))

first = np.zeros((n, n+1))
second = np.zeros((n, n+1))
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[l][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
print(np.sum(second))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = tuple(map(int, input().split()))

first = np.zeros((n, n+1))
second = np.zeros((n, n+1))
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[1][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
print(np.sum(second))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
P = np.array(map(int, input().split()))
ans = 0
for l in range(N):
    for r in range(l, N+1):
        p = P[l:r]
        p.sort(reverse=True)
        ans += p[1]
print(ans)

Submission status: Runtime Error

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

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

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

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

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

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


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

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

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

Submission status: Runtime Error

Solution code:
import bisect
N = int(input())
P = map(int, input().split())
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Submission status: Runtime Error

Solution code:
    N = int(input())
    P = [int(x) for x in input().split()]

    ans = 0
    # [key second,first:gain]のリストを更新していく
    calc_result = {}
    for R in range(1, N):
        first_val = P[R-1]
        second_val = 0
        key_name = "{0},{1}".format(second_val, first_val)
        calc_result[key_name] = 1
        calc_result_new = {}
        for c in calc_result:
            # 値の更新
            second_val, first_val = [int(x) for x in c.split(',')]
            if second_val < P[R] <= first_val:
                second_val = P[R]
            elif first_val < P[R]:
                second_val = first_val
                first_val = P[R]

            ans += second_val * calc_result[c]

            new_key = "{0},{1}".format(second_val, first_val)

            if new_key in calc_result_new:
                calc_result_new[new_key] += calc_result[c]
            else:
                calc_result_new[new_key] = calc_result[c]

        calc_result = calc_result_new

    print(ans)

if __name__ == "__main__":
    main()