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:
#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
  insert(0,pos)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = sum([self.data[i], self.data[i-1]])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = sum([self.data[2*idx+1], self.data[2*idx+2]])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = sum([result, self.data[idx1]])
                if idx2&1 == 1: # idx2が奇数
                    result = sum([result, self.data[idx2]])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = sum([result, self.data[idx1]])
            else: # idx1 + 1 == idx2
                result = sum([result, self.data[idx1], self.data[idx2]])
            
            return result

def find_next(st, idx):
    n = len(st)
    idx_v = st.query(idx, idx)
    right_sum = st.query(idx, n) - idx_v
    if right_sum:
        left = idx
        right = n
        while left + 1 < right:
            mid = (left + right) // 2
            right_sum = st.query(idx, mid) - idx_v
            if right_sum >= 1:
                right = mid
            else:
                left = mid
        return left
    else:
        return n

def find_before(st, idx):
    if idx == 0:
        return -1
    left_sum = st.query(0, idx)
    if left_sum:
        left = 0
        right = idx
        while left + 1 < right:
            mid = (left + right) // 2
            left_sum = st.query(mid, idx)
            if left_sum:
                left = mid
            else:
                right = mid
        return left
    else:
        return -1


N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

a = [0]*N
st = SegmentTree(a)
ans = 0
for i, p in P:
  ir1 = find_next(st, i)
  ir2 = N if ir1==N else find_next(st, ir1)
  il1 = find_before(st, i)
  il2 = -1 if il1==-1 else find_before(st, il1)
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  st.update(i, 1)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a, mode='min'):
        if mode == 'min':
            self.padding = float('inf')
            self.func = min
        elif mode == 'max':
            self.padding = -float('inf')
            self.func = max
        elif mode == 'sum':
            self.padding = 0
            self.func = sum
        
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self.func([self.data[i], self.data[i-1]])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self.func([self.data[2*idx+1], self.data[2*idx+2]])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = self.func([result, self.data[idx1]])
                if idx2&1 == 1: # idx2が奇数
                    result = self.func([result, self.data[idx2]])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = self.func([result, self.data[idx1]])
            else: # idx1 + 1 == idx2
                result = self.func([result, self.data[idx1], self.data[idx2]])
            
            return result

def find_next(st, idx):
    n = len(st)
    idx_v = st.query(idx, idx)
    right_sum = st.query(idx, n) - idx_v
    if right_sum:
        left = idx
        right = n
        while left + 1 < right:
            mid = (left + right) // 2
            right_sum = st.query(idx, mid) - idx_v
            if right_sum >= 1:
                right = mid
            else:
                left = mid
        return left
    else:
        return n

def find_before(st, idx):
    if idx == 0:
        return -1
    left_sum = st.query(0, idx)
    if left_sum:
        left = 0
        right = idx
        while left + 1 < right:
            mid = (left + right) // 2
            left_sum = st.query(mid, idx)
            if left_sum:
                left = mid
            else:
                right = mid
        return left
    else:
        return -1


N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

a = [0]*N
st = SegmentTree(a, 'sum')
ans = 0
for i, p in P:
  ir1 = find_next(st, i)
  ir2 = N if ir1==N else find_next(st, ir1)
  il1 = find_before(st, i)
  il2 = -1 if il1==-1 else find_before(st, il1)
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  st.update(i, 1)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

ans = 0
larger_indexes = [-1, -1, N, N]
for i, p in P:
  idx = bisect.bisect_left(larger_indexes, i)
  ir1, ir2 = larger_indexes[idx], larger_indexes[idx+1]
  il1, il2 = larger_indexes[idx-1], larger_indexes[idx-2]
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  larger_indexes.insert(idx, i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

ans = 0
larger_indexes = [-1, -1, N, N]
for i, p in P:
  idx = bisect.bisect_left(larger_indexes, i)
  ir1, ir2 = larger_indexes[idx], larger_indexes[idx+1]
  il1, il2 = larger_indexes[idx-1], larger_indexes[idx-2]
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  bisect.insort(larger_indexes, i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
list_score = list(map(int, input().split()))
ans = []

for i in range(n-1):
    for j in range(1, n):
        a = list_score[i:j+1]
        a.append(0)
        a.append(0)
        a.sort()
        ans.append(a[-2])

print(sum(ans))

Submission status: Time Limit Exceeded

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

leftMax = [0] * N
rightMax = [0] * N
leftMax[0] = P[0]
rightMax[-1] = P[-1]
for i in range(N - 1):
    leftMax[i + 1] = max(leftMax[i], P[i + 1])
    rightMax[N - 1 - (i + 1)] = max(rightMax[N - 1 - i], P[N - 1 - i])

ans = 0
for i in range(N):
    a, b, c, d = -1, -1, N, N
    p = P[i]
    if leftMax[i] != p:
        for L in range(i - 1, -1, -1):
            if P[L] > p:
                if b == -1:
                    b = L
                elif a == -1:
                    a = L
                else:
                    break
    if rightMax[i] != p:
        for R in range(i + 1, N):
            if P[R] > p:
                if c == N:
                    c = R
                elif d == N:
                    d = R
                else:
                    break
    left = (b - a) * (c - i)
    right = (d - c) * (i - b)
    ans += p * (left + right)

print(ans)

Submission status: Time Limit Exceeded

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


ans = 0
for i in range(N):
    a, b, c, d = -1, -1, N, N
    for L in range(i - 1, -1, -1):
        if P[L] > P[i]:
            if b == -1:
                b = L
            elif a == -1:
                a = L
            else:
                break
    for R in range(i + 1, N):
        if P[R] > P[i]:
            if c == N:
                c = R
            elif d == N:
                d = R
            else:
                break
    left = (b - a) * (c - i)
    right = (d - c) * (i - b)
    ans += P[i] * (left + right)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def compute_sum(int_list):
    curr_second = min(int_list[0], int_list[1])
    curr_max = max(int_list[0], int_list[1])
    total = curr_second
    for r in range(2, len(int_list)):
        curr = int_list[r]
        if curr <= curr_second:
            total += curr_second
        elif curr >= curr_max:
            total += curr_max
            curr_second, curr_max = curr_max, curr
        else:
            total += curr
            curr_second = curr
    return total


n = int(input())
perm = [int(i) for i in input().split()]

total = 0
for l in range(n - 1):
    total += compute_sum(perm[l:])

print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    class BIT():
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
    
    N=int(input())
    P=list(map(int,input().split()))
    P2=[(P[i],i) for i in range(N)]
    P2.sort(reverse=True)
    b=BIT(N)
    
    def nibutan(i,num,ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(i,num,mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(i,num,mid):
        if i>mid:
            if b.sum(i)-b.sum(mid-1) >= num:
                return True
        else:
            if b.sum(mid)-b.sum(i) >= num:
                return True
        return False
    
    ans=0
    for p in P2:
        x=b.sum(p[1])
        y=b.sum(N-1)
        if x>=1 or y-x>=1:
            s=nibutan(p[1],1,-1,p[1])
            t=nibutan(p[1],2,-1,p[1])
            u=nibutan(p[1],1,N,p[1])
            v=nibutan(p[1],2,N,p[1])
            if x>=1:
                ans+=p[0]*(s-t)*(u-p[1]) if s>-1 else 0
            if y-x>=1:
                ans+=p[0]*(v-u)*(p[1]-s) if u<N else 0
        b.add(p[1],1)
    
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    class BIT():
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
    
    N=int(input())
    P=list(map(int,input().split()))
    P2=[(P[i],i) for i in range(N)]
    P2.sort(reverse=True)
    b=BIT(N)
    
    def nibutan(i,num,ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(i,num,mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(i,num,mid):
        if i>mid:
            if b.sum(i)-b.sum(mid-1) >= num:
                return True
        else:
            if b.sum(mid)-b.sum(i) >= num:
                return True
        return False
    
    ans=0
    for p in P2:
        s=nibutan(p[1],1,-1,p[1])
        t=nibutan(p[1],2,-1,p[1])
        u=nibutan(p[1],1,N,p[1])
        v=nibutan(p[1],2,N,p[1])
        if b.sum(p[1])>=1:
            ans+=p[0]*(s-t)*(u-p[1]) if s>-1 else 0
        if b.sum(N-1)-b.sum(p[1])>=1:
            ans+=p[0]*(v-u)*(p[1]-s) if u<N else 0
        b.add(p[1],1)
    
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
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=[-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: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
arr = [int(i) for i in input().split()]
sm = 0
for i in itertools.combinations(range(n), 2):
    a = arr[i[0]:i[1] + 1]
    a.sort()
    sm += a[-2]
print(sm)

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.basesize=len(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]=base[i-self.num]
            for i in range(self.num+self.basesize, self.treesize):self.tree[i]=ini
            #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(self.num-1,-1,-1):
                self.tree[i]=monoid(self.tree[2*i+1],self.tree[2*i+2])
        
        #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
        def max_index(self,index_func):
            #探していく
            i=0
            while i<self.num:
                k=2*i+1
                if index_func(self.tree[k+1]):
                    i=k+1
                    continue
                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 index_func(self.tree[k]):
                    i=k
                    continue
                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
            while i!=0:
                i=(i-1)//2
                temp=self.monoid(self.tree[2*i+1],self.tree[2*i+2])
                if self.tree[i]!=temp:
                    self.tree[i]=temp
                    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*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()