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 examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    class Bit():
        def __init__(self, n):
            n = 1<<(n.bit_length())
            self.size = n
            self.tree = [0] * (n + 1)
            return

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x=1):
            # i==0 はだめ => 全部+1するとか
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考
            i = 0
            s = 0
            step = 1 << (self.size - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i + 1

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

    N = I()
    P = LI()
    Order = [[i+1] for i in range(N)]
    for i,p in enumerate(P):
        Order[i].append(p)
    Order.sort(key=lambda x:x[1],reverse=True)
    #print(Order)
    ans = 0
    bit = Bit(N+2)

    for i,p in Order:
        L = bit.sum(i)
        R = bit.sum(N)-L
        bit.add(i)
        l0, l1, r0, r1 = 0, 0, N+1, N+1
        if L>=2:
            l0 = bit.search(L-1)
        if L>=1:
            l1 = bit.search(L)
        if R>=1:
            r0 = bit.search(L+2)
        if R>=2:
            r1 = bit.search(L+3)
        #print(L,R)
        #print(l0,l1,r0,r1)
        #print(bit.debug(N+2))
        cnt = 0
        if l1>0:
            cnt += (l1-l0)*(r0-i)
        if r0>0:
            cnt += (i-l1)*(r1-r0)
        ans += cnt * p
        #print(ans)
    print(ans)
    return

def examF():
    def bfs(n, e, S):
        W = [0]*(2**n)
        cur = 1
        que = deque()
        que.append(e)
        while cur<2**n:
            now = que.popleft()
            depth = W[now]
            if S[now]<=S[cur]:
                return "No"
            for ne in range(n-depth):
                cur +=1
                W[now+1+ne] = depth+1
                que.append(now+1+ne)
        return "Yes"
    N = I()
    S = LI(); S.sort(reverse=True)
    ans = bfs(N,0,S)
    print(ans)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexTree:  # 1-indexed
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N + 1
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

    def add(self, i, x):
        self.elem[i] += x
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


if __name__ == "__main__":
    N = int(input())
    P = list(map(int, input().split()))
    p_to_i = {p: i for i, p in enumerate(P, start=1)}
    bit = BinaryIndexTree(N)
    bit.add(p_to_i[N], 1)

    ans = 0
    for p in range(N - 1, 0, -1):
        cnt = N - p + 1
        i = p_to_i[p]
        # calc_C
        bit.add(i, 1)
        Bsum = bit.sum(i)
        l2 = max(0, bit.lower_bound(Bsum - 2))
        l1 = bit.lower_bound(Bsum - 1)
        r1 = bit.lower_bound(Bsum + 1)
        r2 = min(N + 1, bit.lower_bound(Bsum + 2))
        CL = (l1 - l2) * (r1 - i)
        CR = (r2 - r1) * (i - l1)
        C = CL + CR
        ans += p * C
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N = int(input())
INF = 10**18
P = list(map(int, input().split()))
I = [-1] * (N + 1)
tree = UnionFind(N + 2)

for i, p in enumerate(P, start=1):
    I[p] = i

ans = 0
used = [False] * (N + 2)
for p in range(1, N):
    i = I[p]

    # p 未満の範囲 [i - left, i + right]
    left = tree.sizeOfSameRoot(i - 1) if used[i - 1] else 0
    right = tree.sizeOfSameRoot(i + 1) if used[i + 1] else 0

    cnt = 0
    leftMx = i - (left + 1)
    if leftMx >= 1 and not used[leftMx]:
        L = tree.sizeOfSameRoot(leftMx - 1) if (leftMx - 1) >= 0 and used[leftMx - 1] else 0
        cnt += (L + 1) * (right + 1)
    rightMx = i + (right + 1)
    if rightMx <= N and not used[rightMx]:
        R = tree.sizeOfSameRoot(rightMx + 1) if (rightMx + 1) <= N and used[rightMx + 1] else 0
        cnt += (left + 1) * (R + 1)
    ans += cnt * p

    used[i] = True
    if used[i - 1]:
        tree.union(i, i - 1)
    if used[i + 1]:
        tree.union(i, i + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))

index=[0]
for i in range(1,n+1):
  index.append(p.index(i)+1)

s=[0,0,index[n],n+1,n+1]
a=[]

for i in reversed(range(1,n)):
  s.append(index[i])
  s.sort()
  t=s.index(index[i])
  
  w=s[t-2]
  x=s[t-1]
  y=s[t+1]
  z=s[t+2]
  c=(x-w)*(y-index[i])+(index[i]-x)*(z-y)
  a.append(i*c)

print(sum(a))

Submission status: Time Limit Exceeded

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+1)):
  pi=p.index(i)+1
  
  s.append(pi)
  s.sort()
  si=s.index(pi)
  
  t.append(pi)
  t.sort()
  ti=t.index(pi)
  
  w=s[si-1]
  x=s[si-2]
  y=t[ti+1]
  z=t[ti+2]
  c=(w-x)*(y-pi)+(pi-w)*(z-y)
  a.append(i*c)
print(sum(a))

Submission status: Time Limit Exceeded

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

ans = 0
for L in range(N-1):
    for R in range(L+1, N):
        if 2 <= len(P[L:R+1]) <= 3:
            seq = sorted(P[L:R+1], reverse=True)
        else:
            if seq[0] > P[R] > seq[1]:
                seq = [seq[0], P[R], seq[1]]
            elif P[R] > seq[0]:
                seq = [P[R], seq[0], seq[1]]
            elif seq[1] > P[R] > seq[2]:
                seq = [seq[0], seq[1], P[R]]
        ans += seq[1]
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for L in range(N-1):
    for R in range(L+1, N):
        ans += sorted(P[L:R+1], reverse=True)[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
p=list(map(int,input().split()))
X=0
for i in range(N-1):
    x1=max(p[i],p[i+1])
    x2=min(p[i],p[i+1])
    X=X+x2
    for j in range(i+2,N):
        x=p[j]
        if(x2<x):
            if(x1<x):
                x2=x1
                x1=x
                X=X+x2
            else:
                x2=x
                X=X+x2
        else:
            X=X+x2
print(X)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())
P=list(map(int,input().split()))
Pindex={i:-1 for i in range(1,N+1)}
for i in range(0,N):
    Pindex[P[i]]=i+1

A=[0,0,N+1,N+1]
ans=0
for i in range(N,0,-1):
    l2=0
    l1=0
    r1=0
    r2=0
    index=Pindex[i]
    a=bisect.bisect_right(A,index)
    r1=A[a]
    r2=A[a+1]
    l1=A[a-1]
    l2=A[a-2]
    ans+=i*(index-l1)*(r2-r1)+i*(l1-l2)*(r1-index)
    bisect.insort_left(A,index)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

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

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
n=100000
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

import sys

input=sys.stdin.readline

N=int(input())
P=list(map(int,input().split()))
Pindex={i:-1 for i in range(1,N+1)}
for i in range(0,N):
    Pindex[P[i]]=i+1

ans=0
for i in range(N,0,-1):
    index=Pindex[i]

    l1=0
    l2=0
    r1=N+1
    r2=N+1

    start=0
    end=index-1
    while end-start>1:
        test=(end+start)//2
        if query(test,index)>0:
            start=test
        else:
            end=test

    if query(end,index)>0:
        l1=end
    else:
        l1=start

    start=0
    end=index-1
    while end-start>1:
        test=(end+start)//2
        if query(test,index)>1:
            start=test
        else:
            end=test

    if query(end,index)>1:
        l2=end
    else:
        l2=start

    start=index+1
    end=N+1
    while end-start>1:
        test=(end+start)//2
        if query(index+1,test+1)>0:
            end=test
        else:
            start=test

    if query(index,start+1)>0:
        r1=start
    else:
        r1=end

    start=index+1
    end=N+1
    while end-start>1:
        test=(end+start)//2
        if query(index+1,test+1)>1:
            end=test
        else:
            start=test

    if query(index+1,start+1)>1:
        r2=start
    else:
        r2=end

    ans+=i*(index-l1)*(r2-r1)+i*(l1-l2)*(r1-index)
    update(index,1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

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

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
n=200000
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

import sys

input=sys.stdin.readline

N=int(input())
P=list(map(int,input().split()))
Pindex={i:-1 for i in range(1,N+1)}
for i in range(0,N):
    Pindex[P[i]]=i+1

ans=0
for i in range(N,0,-1):
    index=Pindex[i]

    l1=0
    l2=0
    r1=N+1
    r2=N+1

    start=0
    end=index-1
    while end-start>1:
        test=(end+start)//2
        if query(test,index)>0:
            start=test
        else:
            end=test

    if query(end,index)>0:
        l1=end
    else:
        l1=start

    start=0
    end=index-1
    while end-start>1:
        test=(end+start)//2
        if query(test,index)>1:
            start=test
        else:
            end=test

    if query(end,index)>1:
        l2=end
    else:
        l2=start

    start=index+1
    end=N+1
    while end-start>1:
        test=(end+start)//2
        if query(index+1,test+1)>0:
            end=test
        else:
            start=test

    if query(index,start+1)>0:
        r1=start
    else:
        r1=end

    start=index+1
    end=N+1
    while end-start>1:
        test=(end+start)//2
        if query(index+1,test+1)>1:
            end=test
        else:
            start=test

    if query(index+1,start+1)>1:
        r2=start
    else:
        r2=end

    ans+=i*(index-l1)*(r2-r1)+i*(l1-l2)*(r1-index)
    update(index,1)

print(ans)

Submission status: Time Limit Exceeded

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.insert(j,i)

print(ans)

Submission status: Time Limit Exceeded

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
    bisect.insort(a,i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
p = [ int(x) for x in input().split()]
x1=0
x2=0

total = 0
x1=p[0]
x2=0
for i in range(n-1):
    if(p[i+1]>x1):
        x2=x1
        x1=p[i+1]
        
    elif(p[i+1]>x2):
        x2=p[i+1]
        
    total+=x2
    
    j=0
    xx1=x1
    xx2=x2
    while(j<i):
        x1_ = x1 in p[:j+1]
        x2_ = x2 in p[:j+1]
        
        if(x1_ and x2_):
            array = sorted(p[j+1:i+2])
            x1 = array[-1]
            x2 = array[-2]
        elif(x1_):
            array = sorted(p[j+1:i+2])
            x1 = array[-1]
            x2 = array[-2]
            
        elif(x2_):
            array = sorted(p[j+1:i+2])
            x1 = array[-1]
            x2 = array[-2]
            
        total+=x2
        j+=1
        
    x1=xx1
    x2=xx2
        
print(total)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
p = [ int(x) for x in input().split()]
x1=0
x2=0

total = 0
for i in range(n-1):
    x1 = max(p[i],p[i+1])
    x2 = min(p[i],p[i+1])
    total+=x2
    
    for j in range(i+2,n):
        if(p[j]>x1):
            x2=x1
            x1=p[j]
        elif(p[j]>x2):
            x2=p[j]
            
        total+=x2
        
print(total)

Submission status: Time Limit Exceeded

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

ls = [-1,-1,N,N]
ans = 0
for i in range(N,0,-1):
    x = P.index(i)
    ind = bisect.bisect(ls,x)
    bisect.insort(ls,x)
    L2 = ls[ind-2]
    L1 = ls[ind-1]
    R1 = ls[ind+1]
    R2 = ls[ind+2]
    L = (L1-L2)*(R1-x)
    R = (R2-R1)*(x-L1)
    ans += i * (L+R)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = [0]*n
    for i in range(n):
        l1[l[i]-1] = i
    ans = 0
    s = [-1,-1,l1[-1],n,n]

    for i in range(n-2,-1,-1):
        c = l1[i]
        now = bisect.bisect_right(s,c)
        a = s[now-2]
        b = s[now-1]
        d = s[now]
        e = s[now+1]
        count = (b-a)*(d-c) + (e-d)*(c-b)
        s.insert(now,c)
        ans += count*(i+1)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = []
    for i in range(n):
        l1.append([l[i],i])
    l1.sort(reverse=True)
    ans = 0
    s = [-1,-1,l1[0][1],n,n]

    for i in range(1,n):
        c = l1[i][1]
        now = bisect.bisect_right(s,c)
        a = s[now-2]
        b = s[now-1]
        d = s[now]
        e = s[now+1]
        count = (b-a)*(d-c) + (e-d)*(c-b)
        s.insert(now,c)
        ans += count*(n-i)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = []
    for i in range(n):
        l1.append([l[i],i])
    l1.sort(reverse=True)
    ans = 0
    s = [-1,-1,l1[0][1],n,n]

    for i in range(1,n):
        now = bisect.bisect_right(s,l1[i][1])
        count = (s[now-1]-s[now-2])*(s[now]-l1[i][1]) + (s[now+1]-s[now])*(l1[i][1]-s[now-1])
        s.insert(now,l1[i][1])
        ans += count*(n-i)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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

# BIT
# Binary Index Tree
# 二分探索

N = int(input())
P = list(map(int, input().split()))
p_to_i = {a: i for i, a in enumerate(P, 1)}


# A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)


# A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx & (-idx)
    return res_sum


# Ai += x O(logN)
def BIT_update(idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += idx & (-idx)
    return


# x <= A1 - Ai となるiの最小値(1-indexed) O(logN)
def BIT_search(x):
    i = 0
    step = 1 << (N.bit_length() - 1)

    while step:
        if i + step <= N and BIT[i + step] < x:
            x -= BIT[i + step]
            i += step

        step >>= 1
    return i + 1


ans = 0
for p in range(N, 0, -1):
    i = p_to_i[p]

    #print("p == ", p, "i =", i)

    # 左,右
    LEFT = BIT_query(i)
    RIGHT = N - p - LEFT

    #print("LEFT,RIGHT : ", LEFT, RIGHT)

    cnt = 0

    # 左に0個 AND 右に0個の時
    if LEFT == 0 and RIGHT == 0:
        BIT_update(i, 1)
        continue

    # a ,,, b ,, i ,, c ,, d
    a = BIT_search(LEFT - 1) if LEFT >= 2 else 0
    b = BIT_search(LEFT) if LEFT >= 1 else 0
    c = BIT_search(LEFT + 1) if RIGHT >= 1 else N + 1
    d = BIT_search(LEFT + 2) if RIGHT >= 2 else N + 1

    if b != 0:
        cnt += (b - a) * (c - i)
    if c != N + 1:
        cnt += (d - c) * (i - b)

    BIT_update(i, 1)
    ans += p * cnt

    #print("a,b,c,d : ", a, b, c, d)
    #print("cnt,score :", cnt, cnt * p)
    #print("ans : ", ans)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, insort_left

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
P = lr()
P_tuple = [(x, i) for i, x in enumerate(P)]
P_tuple.sort(reverse=True)
high_num = []
length = 0
answer = 0
for x, i in P_tuple:
    if length == 0:
        insort_left(high_num, i)
        length += 1
        continue
    index = bisect_left(high_num, i)    
    left = 0; right = 1
    if index > 1:
        left = high_num[index-1] - high_num[index-2]
    elif index == 1:
        left = high_num[0] + 1
    if length == index:
        right = N - i
    else:
        right = high_num[index] - i
    answer += x * left * right
    left = 1; right = 0
    if index > 0:
        left = i - high_num[index-1]
    elif index == 0:
        left = i + 1
    if length - index > 1:
        right = high_num[index+1] - high_num[index]
    elif length - index == 1:
        right = N - high_num[index]
    answer += x * left * right    
    insort_left(high_num, i)
    length += 1
    
print(answer)
#

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, insort_left

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
P = lr()
P_tuple = [(x, i) for i, x in enumerate(P)]
P_tuple.sort(reverse=True)
high_num = []
length = 0
answer = 0
for x, i in P_tuple:
    if length == 0:
        insort_left(high_num, i)
        length += 1
        continue
    index = bisect_left(high_num, i)    
    left = 0; right = 1
    if index > 1:
        left = high_num[index-1] - high_num[index-2]
    elif index == 1:
        left = high_num[0] + 1
    if length == index:
        right = N - i
    else:
        right = high_num[index] - i
    answer += x * left * right
    left = 1; right = 0
    if index > 0:
        left = i - high_num[index-1]
    elif index == 0:
        left = i + 1
    if length - index > 1:
        right = high_num[index+1] - high_num[index]
    elif length - index == 1:
        right = N - high_num[index]
    answer += x * left * right    
    insort_left(high_num, i)
    length += 1
    
print(answer)
#

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
p=list(map(int,input().split()))
locate=[0]*(n+1)

for i in range(n):
    locate[p[i]]=i

a=[-1,-1,n,n]
ans=0
for i in range(n,0,-1):
    k=locate[i]
    q=bisect.bisect_left(a,k)
    a.insert(q,k)
    c=(a[q]-a[q-1])*(a[q+2]-a[q+1])+(a[q-1]-a[q-2])*(a[q+1]-a[q])
    ans+=c*i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    print(Ans)

    return 0

if __name__ == "__main__":
    solve()