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:
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*2+1
            self.tree=[None]*self.treesize
            #segtree[m]以降に代入したい配列を入力していく
            for i in range(self.num, self.num+self.basesize):self.tree[i]=self.base[i-self.num]
            for i in range(self.num+self.basesize, self.treesize):self.tree[i]=self.ini
            #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(self.num-1,-1,-1):
                j=2*i+1
                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):
            #返り値を初期化
            ret=self.ini
            l=lower+self.num
            r=upper+self.num
            while l<r:
                if r%2==0:
                    r-=1
                    ret=self.monoid(ret,self.tree[r])
                if l%2==0:
                    ret=self.monoid(ret,self.tree[l])
                    l+=1
                l//=2
                r//=2
            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([1,2,3],max,0)
    #print(s.tree)
    
    s=segtree([10**6,10**6]+a+[10**6,10**6],max,0)

    def b_search_u(a,b,border):
        ini=a
        while True:
            med=(a+b)//2
            if a==b:return a
            if a+1==b:
                if s.search(ini,a+1)>border:return a
                else:return b
            elif s.search(ini,med+1)>border:b=med
            else:a=med+1

    def b_search_d(a,b,border):
        ini=b
        while True:
            med=(a+b)//2
            if a==b:return a
            elif a+1==b:
                if s.search(b,ini+1)>border:return b
                else:return a
            elif s.search(med,ini+1)>border:a=med
            else:b=med-1

    d=[0]*n
    for i in range(n):
        d[a[i]-1]=i
    ans=0
    for i in range(n-1):
        k1=b_search_u(d[i]+3,n+3,i+1)
        cnt1=min(b_search_u(k1+1,n+4,i+1),n+2)
        k2=b_search_d(1,d[i]+1,i+1)
        cnt2=max(b_search_d(0,k2-1,i+1),1)
        ans+=((k2-cnt2)*(k1-d[i]-2)+(cnt1-k1)*(d[i]-k2+2))*(i+1)
    print(ans)
main()

Submission status: Time Limit Exceeded

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)])
    
        #半開区間[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
        
    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:
                k1=aa
                break
            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:
                cnt1=min(aa,n+2)-k1
                break
            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:
                cnt2=k2-max(aa,1)
                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: Time Limit Exceeded

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)

    def b_search_u(a,b,border):
        ini=a
        while True:
            med=(a+b)//2
            if a==b:return a
            if a+1==b:
                if s.search(ini,a+1)>border:return a
                else:return b
            elif s.search(ini,med+1)>border:b=med
            else:a=med+1

    def b_search_d(a,b,border):
        ini=b
        while True:
            med=(a+b)//2
            if a==b:return a
            elif a+1==b:
                if s.search(b,ini+1)>border:return b
                else:return a
            elif s.search(med,ini+1)>border:a=med
            else:b=med-1

    d=[0]*n
    for i in range(n):
        d[a[i]-1]=i
    ans=0
    for i in range(n-1):
        k1=b_search_u(d[i]+3,n+3,i+1)
        cnt1=min(b_search_u(k1+1,n+4,i+1),n+2)
        k2=b_search_d(1,d[i]+1,i+1)
        cnt2=max(b_search_d(0,k2-1,i+1),1)
        ans+=((k2-cnt2)*(k1-d[i]-2)+(cnt1-k1)*(d[i]-k2+2))*(i+1)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    #from itertools import permutations as p
    n=int(input())
    a=list(map(int,input().split()))
    #n=3
    #a=[n-i for i in range(n)]
    #a=[1,3,2,4,6,5]
    n=len(a)

    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)

    #a,bには下限と上限、valueにはOKな範囲のときはTrue、そうでないときにFalseを返す関数を入れる
    #limは下限を知りたいときはlower、上限を知りたいときはupperを入れる
    def b_search_u(a,b,border):
        ini=a
        while True:
            med=(a+b)//2
            if a==b:return a
            if a+1==b:
                if value_u(a,ini,border):return a
                else:return b
            elif value_u(med,ini,border):b=med
            else:a=med+1

    def value_u(i,ini,border):
        if s.search(ini,i+1)>border:
            return True
        else:
            return False

    def b_search_d(a,b,border):
        ini=b
        while True:
            med=(a+b)//2
            if a==b:return a
            elif a+1==b:
                if value_d(b,ini,border):return b
                else:return a
            elif value_d(med,ini,border):a=med
            else:b=med-1
    def value_d(i,ini,border):
        if s.search(i,ini+1)>border:
            return True
        else:
            return False

    def calc(q):
        d=[0]*n
        for i in range(n):
            d[q[i]-1]=i
        ans=0
        for i in range(n-1):
            k1=n
            cnt1=n
            for j in range(d[i]+1,n):
                if q[j]>i+1:
                    k1=j
                    break
            for j in range(k1+1,n):
                if q[j]>i+1:
                    cnt1=j
                    break
            k2=-1
            cnt2=-1
            for j in range(d[i]-1,-1,-1):
                if q[j]>i+1:
                    k2=j
                    break
            for j in range(k2-1,-1,-1):
                if q[j]>i+1:
                    cnt2=j
                    break
            print(cnt2,k2,d[i],k1,cnt1)
            ans+=((k2-cnt2)*(k1-d[i])+(cnt1-k1)*(d[i]-k2))*(i+1)
        return ans

    def calc2(q):
        d=[0]*n
        for i in range(n):
            d[q[i]-1]=i
        ans=0
        for i in range(n-1):
            k1=b_search_u(d[i]+3,n+4,i+1)
            cnt1=min(b_search_u(k1+1,n+4,i+1),n+2)
            k2=b_search_d(0,d[i]+1,i+1)
            cnt2=max(b_search_d(0,k2-1,i+1),1)
            #print(cnt2-2,k2-2,d[i],k1-2,cnt1-2)
            ans+=((k2-cnt2)*(k1-d[i]-2)+(cnt1-k1)*(d[i]-k2+2))*(i+1)
        return ans
    #print(calc(a))
    print(calc2(a))

    #for i in p(a):
    #    if calc(i)!=calc2(i):
    #        print(i,calc(i),calc2(i))
main()

Submission status: Time Limit Exceeded

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

num2id = [0] * (N+1)
for i in range(N):
    num2id[P[i]] = i+1

used = [0, 0, N + 1, N + 1]

ans = 0
for n in range(N, 0, -1):
    i = num2id[n]
    j = bisect.bisect_left(used, i)
    l2, l1, r1, r2 = used[j - 2], used[j - 1], used[j], used[j + 1]
    # print(i)
    # print(l2, l1, r1, r2)
    ans += n * ((l1 - l2) * (r1 - i) + (i - l1) * (r2 - r1))
    used.insert(j, i)
# print(used)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# tree[i] += 1 O(logN)
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

# sum(tree[1:i+1]) O(logN)
def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

# 二分探索 O(logN)
# 和がx以上となる最小のインデックス(>= 1)を返す
def BIT_search(x):
    # 求めるインデックス
    i = 0
    # 和
    s = 0
    # step = 2^i  (2^i <= N)
    step = 1<<(N.bit_length()-1)
    while step:
        if i+step <= N and s + tree[i+step] < x:
            i += step
            s += tree[i]
        step >>= 1
    # 1-indexed
    return i+1


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

# 1-indexed
P = [None] + [int(x) for x in input().split()]

# p_to_i[i] = P.index(i)
# 1-indexed
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

"""
大きい数から挿入していく
左隣にあるインデックスを取得できるようにしておく
そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ
"""

# BIT (1-indexed)
tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    # 左にある既に書き込んだ数の個数
    L = BIT_sum(c)
    # 右にある既に書き込んだ数の個数
    R = BIT_sum(N) - L
    # tree[c] += 1 
    BIT_add(c)
    # 左側
    a = BIT_search(L-1) if L > 1 else 0
    b = BIT_search(L) if L > 0 else 0
    # 右側
    d = BIT_search(L+2) if R > 0 else N+1
    e = BIT_search(L+3) if R > 1 else N+1

    # xとなる個数
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef

print(answer)

Submission status: Time Limit Exceeded

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()))
B=0
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: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*p=map(int,read().split())
	H=[0,0,n+1,n+1]
	pidx=[0]*(n+1)
	for i in range(n):
		pidx[p[i]]=i+1
	
	pidx.reverse()
	
	
	ans=0
	for i in pidx:
		I=bisect.bisect_left(H,i)
		ans+=p[i-1]*((H[I-1]-H[I-2])*(H[I]-i)+(H[I+1]-H[I])*(i-H[I-1]))
		H.insert(I,i)
	print(ans)
	
	
if __name__ == "__main__":
		main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(int,input().split()))
ans=0
for L in range(N):
    for R in range(L+1,N):
        Q=sorted(P[L:R+1])
        if len(Q)>1:
            ans+=Q[len(Q)-2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# instead of AVLTree
class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    # 0からiまでの区間和
    # 立っているビットを下から処理
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 覆ってる区間すべてに足す
    def add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    # 下からc番目(0-indexed)の数
    # O(log(N))
    def search(self, c):
        c += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max:
            return False
        return ind + 1
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
bit = BITbisect(N)

co_to_ind = [0]*(N+1)
for i in range(N):
    co_to_ind[A[i]] = i+1
    bit.insert(i+1)

ans = 0
for n in range(1, N+1):
    ind = co_to_ind[n]
    seq = bit.bisect_left(ind)
    L = bit.length()
    if seq >= 2:
        l1 = bit.search(seq-1)
        l0 = bit.search(seq-2)
    elif seq == 1:
        l1 = bit.search(seq-1)
        l0 = 0
    else:
        l1 = 0
        l0 = 0
    if L-1 - seq >= 2:
        r1 = bit.search(seq+1)
        r0 = bit.search(seq+2)
    elif L-1 - seq == 1:
        r1 = bit.search(seq+1)
        r0 = N+1
    else:
        r1 = N+1
        r0 = N+1
    #print(n,l0,l1, r1, r0, ((ind-l1)*(r0-r1) + (l1-l0)*(r0-ind)))
    ans += ((ind-l1)*(r0-r1) + (l1-l0)*(r1-ind)) * n
    bit.delete(ind)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


N = int(input())
P = [int(_) for _ in input().split()]
p_i = {p: i + 1 for i, p in enumerate(P)}
SL = SegmentTree([0] * (N + 2), max, 0)
SR = SegmentTree([N + 1] * (N + 2), min, N + 1)
ans = 0
for p in range(N, 0, -1):
    i = p_i[p]
    SL.update(i, i)
    SR.update(i, i)
    il = SL.query(0, i)
    ir = SR.query(i + 1, N + 2)
    if il > 0:
        ill = SL.query(0, il)
        ans += p * (il - ill) * (ir - i)
    if ir < N + 1:
        irr = SR.query(ir + 1, N + 2)
        ans += p * (irr - ir) * (i - il)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = list(map(int, input().split()))
perm = sorted(range(N), key=lambda n:nums[n], reverse=True)

import bisect
found = [-1, N]
total = 0
def sup(index):
    lo = 0; hi = len(found) - 1
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2
        if found[mid] >= index:
            hi = mid - 1
        else:
            lo = mid
    return found[lo]

def inf(index):
    lo = 0; hi = len(found) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if found[mid] <= index:
            lo = mid + 1
        else:
            hi = mid
    return found[lo]
            
for ind in perm:
    if nums[ind] == N: bisect.insort(found, ind); continue
    
    l0 = sup(ind)
    l1 = sup(l0)
    r0 = inf(ind)
    r1 = inf(r0)

    le = (l0 - l1) * (r0 - ind) if l0 != -1 else 0
    ri = (r1 - r0) * (ind - l0) if r0 != N else 0

    total += (le + ri) * nums[ind]
    bisect.insort(found, ind)
print(total)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = np.argsort(P)
left = [i for i in range(N)]
right = [i for i in range(N)]
result = 0
for i in range(1, N):
    k = a[i - 1]
    extend_left = k - 1 >= 0 and P[k - 1] < i
    extend_right = k + 1 < N and P[k + 1] < i
    if extend_left and extend_right:
        L = left[k - 1]
        R = right[k + 1]
    elif extend_left:
        L = left[k - 1]
        R = k
    elif extend_right:
        R = right[k + 1]
        L = k
    else:
        L = k
        R = k
    right[L] = R
    left[R] = L
    if L - 1 >= 0:
        if L - 2 >= 0 and P[L - 2] < i:
            LL = left[L - 2]
        else:
            LL = L - 1
        result += ((L - 1) - LL + 1) * (R - k + 1) * i;
    if R + 1 < N:
        if R + 2 < N and P[R + 2] < i:
            RR = right[R + 2]
        else:
            RR = R + 1
        result += (RR - (R + 1) + 1) * (k - L + 1) * i;
print(result)