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:
import sys
input=sys.stdin.readline

def main():
    N = int(input())
    P = list(map(int, input().split()))
    ans = 0
    for l in range(N-1):
        n1 = 0
        n2 = 0
        for r in range(l+1,N):
            if r-l+1 == 2:
                n1 = max(P[l:r+1])
                n2 = min(P[l:r+1])
            else:
                if P[r] >= n1:
                    n2 = n1
                    n1 = P[r]
                elif P[r] >= n2:
                    n2 = P[r]
#            print(l,r,n1,n2,"=>",n2)
            ans += n2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
s = 0
for l in range(n-1):
  for r in range(n-l-1):
    s += sorted(p[l:l+r+2])[-2]

print(s)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n-1):
  maxx=p[i]
  second=0
  for j in range(i+1,n):
    if j==i+1:
      maxx=max(p[i],p[i+1])
      second=min(p[i],p[i+1])
      ans+=second
      #print(maxx,second)
    elif maxx>p[j]>second:
      second=p[j]
      ans+=second
      #print(maxx,second)
    elif p[j]>maxx:
      second=maxx
      maxx=p[j]
      ans+=second
      #print(maxx,second)
    else:
      ans+=second
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-1):
    for j in range(n-i-1):
        s = sorted(p[i:i+j+2])[::-1]
        ans += s[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P_list = [int(x) for x in input().split()]
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if (i+1 == j):
            tmp = [P_list[i], P_list[j]]
            now = [max(tmp), min(tmp)]
            ans += now[1]
        else:
            new = P_list[j]
            if (new > now[0]):
                ans += now[0]
                now = [new, now[0]]
            elif (new > now[1]):
                ans += new
                now = [now[0], new]
            else:
                ans += now[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# coding: UTF-8

from math import *
import os
import sys

#import scipy.optimize
import numpy as np


##################################################################
if __name__ == "__main__":
    Input = [input() for i in range(2)]
    N = int(Input[0])
    P = list(map(int,Input[1].split()))

    ans = 0
    for L in range(N-1):
        for R in np.arange(L+1,N,1):
                A = np.array(P[L:R+1])
                M = A.argmax()
                A = np.delete(A,M)
                ans += np.amax(A)
                #sP = sorted(P[L:R+1],reverse=True)
                #ans += sP[1]
    print(ans)

Submission status: Time Limit Exceeded

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

for l in range(n-1):
  for r in range(l+1, n):
    p_copy = p[l:r+1]
    p_copy.sort()
    c += p_copy[-2]
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())

x = list(map(int, input().split()))

m = -1
s = -1
ans = 0

for l in range(0,num-1):
  m = max(x[l:l+2])
  s = min(x[l:l+2])
  ans += s
  for r in range(l+2, num):
    if m < x[r]:
      s = m
      m = x[r]
    elif s < x[r]:
      s = x[r]
    ans += s

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
B = list(map(int, input().split()))
ans = 0

for i in range(0, n):
  for j in range(i+2, n+1):
    ans += sorted(B[i:j])[-2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def A():
    print(int(input())**3)

def B():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]

    points = B[A[0]-1]
    previous = A[0]-1
    #print(points)
    for i in range(1, N):
        points += B[A[i]-1]
        if A[i]-1 == previous+1:
            points += C[previous]
        #print(points)
        previous = A[i]-1
    
    print(points)

def C():
    N = int(input())
    B = [int(i) for i in input().split()]

    s = B[0]
    temp = B[0]
    for i in range(1, len(B)):
        if B[i] > temp:
            s += temp
        else:
            s += B[i]
        
        temp = B[i]
    
    s += temp

    print(s)

def E():
    N = int(input())
    P = [int(i) for i in input().split()]
    s = 0
    for i in range(N-1):
        for j in range(i+1, N):
            temp = P[i:j+1]
            del temp[temp.index(max(temp))]
            m = max(temp)
            s += m
            if m == N-1:
                #print("s")
                s += m*(N-(j+1))
                break

            #print(i, j, max(temp), temp)

    print(s)

E()

Submission status: Time Limit Exceeded

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

ans = 0
for x in range(0, N-1):
    for y in range(x+1, N):
        temp = p[x : y + 1]
        temp.sort(reverse=True)

        ans += temp[1]

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n-1):
  for j in range(len(tmp)):
    if tmp[j][0] <= a[i+1]:
      tmp[j][1] = tmp[j][0]
      tmp[j][0] = a[i+1]
    if tmp[j][1] <= a[i+1] < tmp[j][0]:
      tmp[j][1] = a[i+1]
    #print("a", tmp)
    ans += tmp[j][1]
  tmp.append([max(a[i], a[i+1]), min(a[i], a[i+1])])
  ans += min(a[i], a[i+1])
  #print("b", a[i+1])
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    #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
    ########################################################
    ##初期化（要素は一つ入れておく）
    
    #avl_key:値,avl_left:左の子のindex,avl_right:右の子のindex
    #balance[i]: {"Even":0,"Left":-1,"Right":1}
    
    #avl_keyには初めに何か加えておく
    n = int(input())
    p = list(map(int,input().split()))
    q = [0]*(n+1)
    for i in range(n):
        q[p[i]] = i+1
    
    avl_key = [q[n]]
    avl_left = [None]*(n+1)
    avl_right = [None]*(n+1)
    balance = [0]*n
    
    ans = 0
    
    for i in range(n-1,0,-1):
        cnt = 0
        v = q[i]
        lo = search_lower(0,v,None)
        hi = search_higher(0,v,None)
        #print(lo,hi)
        if lo:
            lo2 = search_lower(0,lo,0)
            t = lo-lo2
            if hi:
                t *= hi - v
            else:
                t *= n+1 - v
            cnt += t
        if hi:
            hi2 = search_higher(0,hi,n+1)
            t = hi2 - hi
            if lo:
                t *= v - lo
            else:
                t *= v
            cnt += t
        #print(cnt)
        ans += i*cnt
        insert(0,v)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

answer = 0

for l in range(n-1):
    for r in range(l+1,n):
        number_list = p[l:r+1]
        number_list.remove(max(number_list))
        second_largest = max(number_list)
        answer += second_largest

print(answer)

Submission status: Time Limit Exceeded

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

from heapq import nlargest
sums = 0
for i in range(N-1):
    for j in range(i+1,N):
        sums += nlargest(2,P[i:j+1])[1]

print(sums)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
f=0
b=[]
t=0
c=[]
for i in range(n-1):
 for l in range(i+1,n):
  b=p[i:l+1]
  c.append(sorted(set(b))[-2])
print(sum(c))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [int(i) for i in input().split()]

sum = 0

for i in range(n-1):
    first = 0
    second = 0
    if p[i] > p[i+1]:
        first = p[i]
        second = p[i+1]
    else:
        first = p[i+1]
        second = p[i]
    sum += second
    for j in range(i+2,n):
        if p[j] > first:
            second = first
            first = p[j]
            sum += second
        elif p[j] > second:
            second = p[j]
            sum += second
        else:
            sum += second

print(sum)

Submission status: Time Limit Exceeded

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

for i in range(N):
    j = 1
    while i + j < N:
        if j == 1:
            second = min(P[i:i+2])
            first = max(P[i:i+2])
        else:
            if second < P[i+j]:
                if first > P[i+j]:
                    second = P[i+j]
                else:
                    second = first
                    first = P[i+j]
        result += second
        j += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
nlis = [0]*N

for i,j in enumerate(map(int,input().split())):
    nlis[N-j] = i

bis = [-1,-1,N,N]

ans = 0
for i,j in enumerate(nlis):
    inser = bisect.bisect_left(bis,j)
    bis.insert(inser,j)
    lis = bis[inser-2:inser+3]
    foo = (lis[4]-lis[3])*(lis[2]-lis[1]) + (lis[3]-lis[2])*(lis[1]-lis[0])
    ans += foo*(N-i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
P = list(map(int, input().split()))
l1 = [0]*n
l2 = [0]*n
r1 = [0]*n
r2 = [0]*n
tot = 0
for i in range(n):
  if P[i] == n:
    pass
  else:
    foundfirst = False
    foundsecond = False
    j = i
    while not (foundfirst and foundsecond):
      j -= 1
      if j == -1:
        if foundfirst:
          foundsecond = True
          l2[i] += 1
        else:
          l1[i] += 1
          foundfirst = True
          foundsecond = True
      elif P[j] > P[i]:
        if foundfirst:
          foundsecond = True
          l2[i] += 1
        else:
          l1[i] += 1
          foundfirst = True
      else:
        if foundfirst:
          l2[i] +=1
        else:
          l1[i] += 1
    foundfirst = False
    foundsecond = False
    j = i
    while not (foundfirst and foundsecond):
      j += 1
      if j == n:
        if foundfirst:
          foundsecond = True
          r2[i] += 1
        else:
          r1[i] += 1
          foundfirst = True
          foundsecond = True
      elif P[j] > P[i]:
        if foundfirst:
          foundsecond = True
          r2[i] += 1
        else:
          r1[i] += 1
          foundfirst = True
      else:
        if foundfirst:
          r2[i] +=1
        else:
          r1[i] += 1
for i in range(n):
  tot += (l1[i]*r2[i]+l2[i]*r1[i])*P[i]
print(tot)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
P = list(map(int,input().split()))
ans = 0
tmp = P
for i in range(n-1):
  for j in range(i+1,n):
    tmp = P[i:j+1]
    tmp.sort()
    ans += tmp[-2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
P1 = list(map(int,input().split()))
a = 0

for i,j in combinations(P1,2):
  l,r = sorted([i,j])
  P2 = P1[l-1:r]
  P2.remove(max(P2))
  a+=max(P2)

print(a)

Submission status: Time Limit Exceeded

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

    ans = 0

    for l in range(N - 1):
        for r in range(l + 1, N):
            if r == l + 1:
                two = min(P[l], P[r])
                one = max(P[l], P[r])
            else:
                tmp = one
                one = max(tmp, P[r])
                tmp = min(tmp, P[r])
                two = max(tmp, two)

            ans += two

    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
p = list(map(int, input().split()))
sum = 0
for L in range(1,n):
  end = 0
  tmp = p[L-1:]
  tmp.sort(reverse=True)
  second_max = tmp[1]
  for R in range(L+1,n+1):
    if end == 1:
      sum += second_max
    else:
    	tmp = p[L-1:R]
    	tmp.sort(reverse=True)
    	sum += tmp[1]
    	if tmp[1] == second_max:
      		end = 1

print(sum)

Submission status: Time Limit Exceeded

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

def getrank(first,second,val):
  if val>first:
    return val,first
  elif val>second:
    return first,val
  else:
    return first,second

sum=0
for i in range(0,n-1):
  first=max(p[i],p[i+1])
  second=min(p[i],p[i+1])
  sum=sum+second
  for j in range(i+2,n):
    res=getrank(first,second,p[j])
    first,second=res[0],res[1]
    sum=sum+second

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
P = list(map(int,input().split()))
sum = 0
heap = []
for L in range(N-1):
    heapq.heappush(heap,-(P[L]))
    for R in range(L+1,N):
        heapq.heappush(heap,-(P[R]))
        S = heapq.heappop(heap)
        sum -= heap[0]
        heapq.heappush(heap,S)
    heap = []
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(int, input().split()))
Sum=0
for x in range(0,N-1):
    for y in range(x+1,N):
        if y==x+1:
            if P[x]>P[x+1]:
                F=P[x]
                S=P[x+1]
                Sum=Sum+S
            elif P[x]<P[x+1]:
                F=P[x+1]
                S=P[x]
                Sum=Sum+S
        else:
            if P[y]<S:
                Sum=Sum+S
            elif P[y]>S and P[y]<F:
                S=P[y]
                Sum=Sum+S
            else:
                S=F
                F=P[y]
                Sum=Sum+S
print(Sum)

Submission status: Time Limit Exceeded

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

for i in range(n-1):
  for j in range(i+1,n):
    p_s = p[i:j+1]
    x.append(sorted(p_s)[-2])

print(sum(x))

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())
P = list(map(int, sys.stdin.readline().split()))
ans = 0
for i in range(N-1):
    fir = P[i]
    sec = 0
    for j in range(i+1, N):
        if fir < P[j]:
            sec = fir
            fir = P[j]
        elif sec < P[j]:
            sec = P[j]
        ans += sec
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#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
########################################################
##初期化（要素は一つ入れておく）

#avl_key:値,avl_left:左の子のindex,avl_right:右の子のindex
#balance[i]: {"Even":0,"Left":-1,"Right":1}

#avl_keyには初めに何か加えておく
n = int(input())
p = list(map(int,input().split()))
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1

avl_key = [q[n]]
avl_left = [None]*(n+1)
avl_right = [None]*(n+1)
balance = [0]*n

ans = 0

for i in range(n-1,0,-1):
    cnt = 0
    v = q[i]
    lo = search_lower(0,v,None)
    hi = search_higher(0,v,None)
    #print(lo,hi)
    if lo:
        lo2 = search_lower(0,lo,0)
        t = lo-lo2
        if hi:
            t *= hi - v
        else:
            t *= n+1 - v
        cnt += t
    if hi:
        hi2 = search_higher(0,hi,n+1)
        t = hi2 - hi
        if lo:
            t *= v - lo
        else:
            t *= v
        cnt += t
    #print(cnt)
    ans += i*cnt
    insert(0,v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    P = list(map(int, input().split()))
    ans = 0
    for l in range(N-1):
        l += 1
        #for r in np.arange(start=l+1, step=1, stop=N+1):
        for r in range((N+1)-(l+1)):
            r += l + 1
            #print(l,r)
            x_cand = P[l-1:r]
            x_cand.sort(reverse=True)
            #print(x_cand)
            x_lr = x_cand[1]
            ans += x_lr

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#N = 8
#P = [8, 2, 7, 3, 4, 5, 6, 1]
N=int(input())  
P=list(map(int, input().split())) 
#L = 0
X = 0

for L in range(N-1):
    for R in range(L+1, N):
        #print(np.sort(a))
        #print(np.sort(a)[-2])
        Xi = np.sort(P[L:R+1])[-2]
        X += Xi
print(X)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
f=0
b=[]
t=0
c=[]
for i in range(n-1):
 for l in range(i+1,n):
  b=p[i:l+1]
  t=max(b)
  b.remove(t)
  for j in range(b.count(t)):
   b.remove(t)
  c.append(max(b))
print(sum(c))

Submission status: Time Limit Exceeded

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n=int(input())
p=list(map(int,input().split()))
cnt=0

for i in range(0,n-1):
	for j in range(i+1,n):
		s=p[i:j+1]
		s_s=sorted(s)
		s_ss=s_s.pop()
		cnt+=s_s[j-i-1]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import islice, combinations


def nth(iterable, n, default=None):
    return next(islice(iterable, n, None), default)


N = int(input())
P = tuple(map(int, input().split(" ")))

s = 0
for L, R in combinations(range(1, N + 1), 2):
    ll = sorted(islice(P, L - 1, R), reverse=True)
    s += nth(ll, 1)
else:
    print(s)

Submission status: Time Limit Exceeded

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

print(sum([sum([sorted(p[l : l + r + 2])[-2] for r in range(n - l - 1)]) for l in range(n -1)]))

Submission status: Time Limit Exceeded

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

ans=0
for l in range(n-1):
  for i in range(1,n-l):
    if i==1:
      b2=min(p[l],p[l+1])
      b1=max(p[l],p[l+1])
    else:
      if p[l+i]>b1:
        b2=b1
        b1=p[l+i]
      elif p[l+i]>b2:
        b2=p[l+i]
      
    ans+=b2
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[[0]*(N+1) for i in range(N+1)]
C=[[0]*(N+1) for i in range(N+1)]
total = 0
for i in range(1,N):
    B[i][i+1]=min(A[i],A[i-1])
    C[i][i+1]=max(A[i],A[i-1])
    total+=B[i][i+1]
for i in range(1,N):
    for j in range(i+2,N+1):    
            B[i][j]=max(B[i][j-1],min(C[i][j-1],A[j-1]))
            C[i][j]=max(C[i][j-1],A[j-1])
            total+=B[i][j]
print(total)

Submission status: Time Limit Exceeded

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

cnt = 0
for l in range(n-1):
  for r in range(n -l -1):
    lst = p[l : l + r + 2]
    cnt += sorted(lst)[-2]
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())
Data = [ 0 for i in range(N)]
TmpData = [ 0 for i in range(N)]

Tmp = []
Tmp = input().rstrip().split(' ')
for i in range(N):
  Data[i] = int(Tmp[i])

Ans = 0

for i in range(N):
  for j in range(i+1,N):
    TmpData = Data[i:j+1]
    TmpData.sort(reverse=True)
#    print(TmpData)
    Ans += TmpData[1]

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

for i in range(N-1):
    for j in range(i+1, N):
        P_sort = sorted(P[i:j+1])
        X += P_sort[-2]

print(X)

Submission status: Time Limit Exceeded

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

ans = 0
for l in range(n-1):
    x1 = max(p[l],p[l+1])
    x2 = min(p[l],p[l+1])
    ans += x2
    for r in range(l+2,n):
        if x2 == n-1:
            ans += x2*(n-r)
            break
        if p[r]<x2:
            ans += x2
        elif x2<p[r]<x1:
            ans += p[r]
            x2 = p[r]
        elif p[r]>x1:
            ans += x1
            x2 = x1
            x1 = p[r]
print(ans)