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:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, insort_left
INF = float("inf")


def solve(N: int, P: "List[int]"):

    # 番号pは何番目か 0-index
    rev = [0]*(N+1)
    for i, p in enumerate(P):
        rev[p] = i

    ans = 0
    seq = [rev[N]]
    for i in range(N-1, 0, -1):
        j = bisect_left(seq, rev[i])
        seq.insert(j, rev[i])
        # print(seq, j)
        if j != 0:
            L, R = seq[j-1], seq[j]
            LL = seq[j-1]-seq[j-2] if j-2 >= 0 else seq[j-1]+1
            RR = seq[j+1]-seq[j] if j+1 <= N-i else N-seq[j]
            ans += i*(LL*RR)
            # print("addA", i*(LL*RR), LL, RR)

        if j != N-i:
            L, R = seq[j], seq[j+1]
            LL = seq[j]-seq[j-1] if j-1 >= 0 else seq[j]+1
            RR = seq[j+2]-seq[j+1] if j+2 <= N-i else N-seq[j+1]
            ans += i*(LL*RR)
            # print("addB", i*(LL*RR), LL, RR)

        # print("ans", ans)
        # if i == 5:
        # break
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

temp = [sorted(P[i:j+1])[-2] for i in range(0, n-1) for j in range(i+1, n)]

print(sum(temp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP = [int(val) for val in input().split()]

l = 0
r = 2
xlr = 0
tempMax = tempMax2 = max2 = 0
while (l < n - 1):
	tempMax2 = min(ListP[l : l + 2])
	xlr += tempMax2
	tempMax = max(ListP[l : l + 2])
	while (r < n):
		if (tempMax2 < ListP[r]):
			if (tempMax < ListP[r]):
				tempMax2 = tempMax
				tempMax = ListP[r]
			else:
				tempMax2 = ListP[r]
		if (tempMax2 == max2):
			xlr += (n - r) * max2
			break
		xlr += tempMax2
		r += 1
	if (l == 0):
		max2 = tempMax2
	l += 1
	r = l + 2
print(xlr)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for L in range(N-1):
    Xs = [np.sort(P[L:R+1])[-2] for R in range(L+1, N)]
    X_sum_one = np.sum(Xs)
    newX += X_sum_one
print(newX)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
sum_ =0 
for l in range(N-1):
  for r in range(l+1,N):
    for i in range(l,r+1):
      if i == l:
        first = P[i]
        second = -100000000
      else:
        if P[i]>first:
          second = first
          first = P[i]
        elif P[i]>second:
          second = P[i]
    sum_ += second
print(sum_)

Submission status: Time Limit Exceeded

Solution code:
def calc(N, P):
    x = 0
    Q = [
        [P[i], 0]
        for i in range(N)
    ]
    for i in range(1, N):
        for j in range(N - i):
            l = sorted(set(Q[j] + Q[j + 1]), key=lambda x: -x)
            Q[j] = [l[0], l[1]]
            x += Q[j][1]
    return x


N = int(input())
P = [int(s) for s in input().split()]
print(calc(N, P))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int,input().split()))
num = (n * (n-1)) // 2
L = 0
R = 1
ans = 0

def second_largest(numbers):
    count = 0
    m1 = m2 = float('-inf')
    for x in numbers:
        count += 1
        if x > m2:
            if x >= m1:
                m1, m2 = x, m1            
            else:
                m2 = x
    return m2 if count >= 2 else None


for i in range(num):
    num_list = p[L:R+1]
    ans += second_largest(num_list)
    if R != n-1:
      R += 1
    elif R == n-1 and L != n-2:
      L += 1
      R = L+1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
def Xfind(L, R, P):
    return int(list(sorted(P[L:R+1]))[-2])

sum = 0
for l in range(N-1):
    for r in range(l+1, N):
        sum += Xfind(l, r, P)

print(sum)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
n=int(input())
p=list(map(int,input().split()))
d={}
for i in range(n):
    d[p[i]]=i
s=[-1,-1,d[n],n,n]
c=0
for i in range(n-1,0,-1):
    g=bisect_left(s,d[i])
    c+=i*((s[g]-d[i])*(d[i]-s[g-2])+(s[g+1]-d[i])*(d[i]-s[g-1])-2*(s[g]-d[i])*(d[i]-s[g-1]))
    s.insert(g,d[i])
print(c)

Submission status: Time Limit Exceeded

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

ans = 0
for L in range(N-1):
    if P[L] > P[L+1]: No1, No2 = P[L], P[L+1]
    else:   No1, No2 = P[L+1], P[L]
    ans += No2

    for R in range(L+2, N):
        if P[R] > No1:  No1, No2 = P[R], No1
        elif P[R] > No2:    No2 = P[R]
        ans += No2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = int(input())
n= list(map(int,(input().split())))
ans=0
for i in range(len(n)-1):
    for j in range(i+2,len(n)+1):
        ans+=sorted(n[i:j])[::-1][1]


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
P = list(map(int,input().split()))
ans = 0
tmp1 = 0
tmp2 = 0
for i in range(n-1):
  tmp1 = max(P[i+1],P[i])
  tmp2 = min(P[i+1],P[i])
  #print(tmp1,tmp2)
  for j in range(i+1,n):
    if j > i+1:
      if P[j] > tmp1:
        #print('f')
        tmp2 = tmp1
        tmp1 = P[j]
      elif P[j] > tmp2:
        #print('d')
        tmp2 = P[j]
    ans += tmp2
    #print(ans,i,j,tmp1,tmp2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
P_list = list(map(int, input().split()))

# rev_P_list = []
# for P in (reversed(P_list)):
#     rev_P_list.append(P)

x_dic = {}
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if j == i + 1:
            x_dic["{}_{}".format(i, j)] = sorted([P_list[i], P_list[j]], reverse=True)
            ans += x_dic["{}_{}".format(i, j)][1]
        else:
            if P_list[j] > x_dic["{}_{}".format(i, j - 1)][1]:
                tmp_list = [t for t in x_dic["{}_{}".format(i, j - 1)]]
                tmp_list.append(P_list[j])
                tmp_list = sorted(tmp_list, reverse=True)
                x_dic["{}_{}".format(i, j)] = tmp_list[::1]
            else:
                x_dic["{}_{}".format(i, j)] = x_dic["{}_{}".format(i, j - 1)]
            ans += x_dic["{}_{}".format(i, j)][1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
N = int(input())
l = list(map(int,input().split()))


count = 0
ans = 0
before_list = []
for i in range(N-1):
    a = min(l[i],l[i+1])
    b = max(l[i],l[i+1])
    before_list.append((a,b))
    ans = ans + a
before_list = numpy.array(before_list)
##N回この作業をする
while(count < N-2):
    after_list = []
    for i in range(len(before_list)-1):
        a1 = before_list[i][0]
        a2 = before_list[i][1]
        b1 = before_list[i+1][0]
        b2 = before_list[i+1][1]
        if (a2 == b2) :
            a = max(a1,b1)
            b = b2
        else :
            a = min(a2,b2)
            b = max(a2,b2)
        after_list.append((a,b))
        ans = ans + a
    before_list = numpy.array(after_list)
    count = count + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n = int(stdin.readline().rstrip())
p = list(map(int, input().split()))

ans = 0

ll = []
lll = []
lll2 = []

ll.append(p[0])
for i in range(len(p)-1):
    ll.append(p[i+1])
    lll.append(sorted(ll))
    ans += lll[i][i]

#print(ll)
#print(lll)

for l in range(len(p)-1):
    for r in range(l+1, len(p)-1):
        #print(l,r,lll[r])
        lll[r].remove(p[l])
        ans += lll[r][-2]        

#print(ll)
#print(lll)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = list(map(int,input().split()))
ans = 0
for i in range(1,a):
    for j in range(1,a+1):
        if i < j:
            c = b[i-1:j]
            c.sort()
            c.reverse()
            ans += c[1]        
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
p = list(map(int,input().split()))
count = 0
for l in range(n-1):
  q = sorted([p[l],p[l+1]])
  m1 = q[1]
  m2 = q[0]
  for r in range(l+1,n):    
    if p[r] > m1:
      m2 = m1
      m1 = p[r]
      count += m2
    elif m2 > p[r]:
      count += m2
    elif m1 == p[r] or m2 == p[r]:
      count += m2
    else:
      m2 = p[r]
      count += m2
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy
N= int(input())
P = [int(i) for i in input().split()]
max = 0
secmax = 0
S = []

for i in range(N-1):
    if P[i] >= P[i+1]:
        max = P[i]
        secmax = P[i+1]
    else:
        secmax = P[i]
        max = P[i+1]
    S.append(secmax)
    for j in range(i+2, N):
        if P[j] >= max:
            secmax = copy.copy(max)
            max = P[j]
        elif P[j] >= secmax:
            secmax = P[j]
        S.append(secmax)
print(sum(S))

Submission status: Time Limit Exceeded

Solution code:
import copy
n=int(input())
p=list(map(int,input().split()))
goukei=0
for i in range(n-1):
  for s in range(i+1,n):
    pp=copy.deepcopy(p)
    ppp=pp[i:s+1]
    ppp.remove(max(ppp))
    goukei=goukei+max(ppp)
print(goukei)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = na()
ans = 0

for i in range(n):
    #hidari
    h1 = 1
    h2 = 0
    f = False
    for j in reversed(range(i)):
        if not f:
            if p[j] < p[i]:
                h1 += 1
            else:
                h2 += 1
                f = True
        else:
            if p[j] < p[i]:
                h2 += 1
            else:
                break
    #migi
    m1 = 1
    m2 = 0
    f = False
    for j in range(i+1,n):
        if not f:
            if p[j] < p[i]:
                m1 += 1
            else:
                m2 += 1
                f = True
        else:
            if p[j] < p[i]:
                m2 += 1
            else:
                break
    ans += p[i]*(h1*m2+m1*h2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())

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

r1 = 0
t1 = 0
t2 = 0

for i1 in range(n1 - 1):
    for i2 in range(n1 - i1 - 1):
        if i2 == 0:
            t1 = max(n2[i1], n2[i1 + 1])
            t2 = min(n2[i1], n2[i1 + 1])
            r1 += t2 
        else:
            if n2[i1 + i2 + 1] > t1:
                t2 = t1
                t1 = n2[i1 + i2 + 1]
            elif n2[i1 + i2 + 1] > t2:
                t2 = n2[i1 + i2 + 1]
            r1 += t2

print(r1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
p = list (map(int, input().split()))
ans = 0

for i in range(0,n):
    first_max = p[i]
    second_max = p[i]
    for j in range(i+1,n):
        if j == i+1:
            if p[i] <p[j]:
                first_max = p[j]
            else:
                second_max = p[j]
        else:
            if first_max < p[j]:
                second_max = first_max
                first_max = p[j]
            elif  second_max < p[j]:
                second_max = p[j]
        # print(p[i],p[j],second_max)
        ans += second_max

print(ans)

Submission status: Time Limit Exceeded

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

res = 0
top, sec = 0,0
for i in range(N-1):
    top, sec = max(L[i], L[i+1]), min((L[i], L[i+1]))
    res += sec
    for j in range(i+2, N):
        if L[j] > top:
            top, sec = L[j], top
            res += sec
        elif L[j] < sec:
            res += sec
        else:
            sec = L[j]
            res += sec
print(res)

Submission status: Time Limit Exceeded

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

n=int(input())
b=input().split()
for i in range(n):
    b[i]=int(b[i])

def main(l,m1,m2,c,s):
    c+=1
    #print(m1,m2,s,c)
    while c<n-l:
        if c==1:
            if b[l]>b[l+1]:
                m1=b[l]
                m2=b[l+1]
                s+=m2
                c+=1
            else:
                m1=b[l+1]
                m2=b[l]
                s+=m2
                c+=1
            #print(m1,m2,s,c)
        elif b[l+c]>m1:
            m2=m1
            m1=b[l+c]
            s+=m2
            c+=1
        elif b[l+c]>m2:
            m2=b[l+c]
            s+=m2
            c+=1
        else:
            s+=m2
            c+=1
    return s

s1=0
for i in range(n-1):
    s=main(i,0,0,0,0)
    #print(s)
    s1+=s
    #print(s,s1)
print(s1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
P=list(map(int, input().split()))
l=[]
for i in range(N):
    l.append([P[i],i+1])
l.sort(reverse=True)
a=0
p=[0,0,N+1,N+1]
for i in range(N):
    d=bisect.bisect_left(p,l[i][1])
    a+=((p[d-1]-p[d-2])*(p[d]-l[i][1])+(l[i][1]-p[d-1])*(p[d+1]-p[d]))*(N-i)
    p.insert(d,l[i][1])
print(a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):

    sum = 0
    for l in range(N - 1):
        for r in range(l + 1, N):
            nums = P[l:r + 1]
            m1 = max(nums)
            nums.remove(m1)
            sum += max(nums)
    print(sum)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()

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(1, N):
        if i >= j:
            continue
        tmp = P[i:j+1]
        tmp.sort()
        ans += tmp[-2]
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):
    temp = P[i:N]
    t = 0
    prev = 0
    max_t = 0
    for a, b in enumerate(temp):
        if a == 0:
            prev = b
            continue
        elif a == 1:
            t = min(prev, b)
            max_t = max(prev, b)
        else:
            if t < b:
                if b > max_t:
                    t = max_t
                    max_t = b
                else:
                    t = b
        ans += t
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def second_max(arr):
    return sorted(arr)[-2]


N = int(input())

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

result = 0
for L in range(N-1):
    C = [-1]

    for i in range(len(C)):
        if C[i] < P[L]:
            C.insert(i, P[L])
            break

    for R in range(L+1, N):
        for i in range(len(C)):
            if C[i] < P[R]:
                C.insert(i, P[R])
                break
        result += C[1]

print(result)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
ans=0
for l in range(1,n):
    for r in range(l+1,n+1):
        q=p[l-1:r]
        q_sorted=sorted(q)
        #print(q_sorted)
        x=q_sorted[r-l-1]
        #print(x)
        ans+=x
print(ans)

Submission status: Time Limit Exceeded

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

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

print(sumX)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    n = int(input())
    P = [int(i) for i in input().split()]
    res = 0
    print(sum([sorted(P[i : j + 1])[-2] for i in range(n) for j in range(i + 1, n)]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def ruiseki(one,two):
  sorte=sorted(one+[two],reverse=True)
  return [sorte[0],sorte[1]]

N=int(input())
P=[int(i) for i in input().split()]
ans=0
for l in range(N):#左端,Rはl+1からのスタート
  prev=[P[l]]
  max2nd=[]
  for r in range(l+1,N):
    prev=ruiseki(prev,P[r])
    max2nd.append(prev)
  ans+=sum([b for a,b in max2nd])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

SUM = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    Pcopy = P
    Pcopy2 = Pcopy[i:j+1]
    Pcopy2.remove(max(Pcopy2))
    SUM += max(Pcopy2)

print(SUM)

Submission status: Time Limit Exceeded

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

def getX(l, r):
    temp = p[l-1:r]
    temp.sort()
    return temp[-2]

ans = 0

for l in range(1, n):
    for r in range(l+1, n+1):
        ans += getX(l, r)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

result=0
sum_list=[P[i:i+j+2][np.argsort(P[i:i+j+2])[-2]] for i in range(N) for j in range(N-1-i)]
print(np.sum(sum_list))

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):
    max2 = min(P[l],P[l+1])
    max1 = max(P[l],P[l+1])
    for r in range(l+1,N):
        if r == l+1:
            pass
        elif P[r] > max2:
            if P[r] > max1:
                max2 = int(max1)
                max1 = P[r]
            else:
                max2 = P[r]
        ans+=max2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int,input().split()))
m = 0
for i in range(n-1):
    for j in range(i+1,n):
        t = p[i:j+1]
        t.remove(max(t))
        m += max(t)
print(m)

Submission status: Time Limit Exceeded

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

for i in range(0,n):
    first_max = p[i]
    second_max = p[i]
    for j in range(i+1,n):
        if j == i+1:
            if p[i] <p[j]:
                first_max = p[j]
            else:
                second_max = p[j]
        else:
            if first_max < p[j]:
                second_max = first_max
                first_max = p[j]
            elif  second_max < p[j]:
                second_max = p[j]
        # print(p[i],p[j],second_max)
        ans += second_max

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n-1):
    for j in range(2, n-i+1):
        l = p[i:i+j]
        score.append(sorted(l)[-2])
print(sum(score))

Submission status: Time Limit Exceeded

Solution code:
#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):
        a = P[L:R+1]#.sort()
        a.sort()
        #print(np.sort(a))
        #print(np.sort(a)[-2])
        Xi = a[-2]
        X += Xi
print(X)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np

n = int(stdin.readline().rstrip())
p_ary = np.array([int(x) for x in stdin.readline().rstrip().split()])
cum = 0

def x_lr(l, r):
  m = np.argmax(p_ary[l:r+1])
  ind = np.ones(r-l+1, dtype=bool)
  ind[m] = False
  m2 = np.max(p_ary[l:r+1][ind])
  return m2

for l in range(n-1):
  for r in range(l+1, n):
    cum += x_lr(l, r)
    
print(cum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P_list = list(int(Pi) for Pi in input().split(' '))

global_list=[]
num=0

for i in range(N-1):
  local_list=[]
  if P_list[i] >= P_list[i+1]:
    local_list.append(P_list[i])
    local_list.append(P_list[i+1])
  else:
    local_list.append(P_list[i+1])
    local_list.append(P_list[i])
    
  global_list.append(local_list)
  

j=2
while True:
  if j>N: break
    
  for i in range(len(global_list)):
    num+=global_list[i][1]
    #print(global_list)
    
    
    if i == len(global_list)-1:
      global_list.pop(-1)
    else:
      #print(P_list[i+j])
      if P_list[i+j] >= global_list[i][0]:
        global_list[i][1]=global_list[i][0]
        global_list[i][0]=P_list[i+j]
      elif (P_list[i+j] >= global_list[i][1]) and (P_list[i+j] < global_list[i][0]):
        global_list[i][1]=P_list[i+j]
      else:
        pass
    
  j+=1
    
print(num)

Submission status: Time Limit Exceeded

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

y = 0 # max
x = 0 # second max
counter = 0 # sum x
for l in range(N-1):
    for r in range(l+1, N):
        if l+1 == r: # init
            y = max(P[l], P[r])
            x = min(P[l], P[r])
        else:
            if P[r] > x and P[r] > y:
                x = y
                y = P[r]
            elif P[r] > x and P[r] < y:
                x = P[r]
        counter += x
print(counter)

Submission status: Time Limit Exceeded

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

result = 0

for i in range(N-1):
    if P[i+1] >= P[i]:
        max_first = P[i+1]
        max_second = P[i]
        result += max_second
    else:
        max_first = P[i]
        max_second = P[i+1]
        result += max_second

    if (N-1 >= i+2):
        for j in range(i+2, N):
            if (P[j] > max_first) & (P[j] > max_second):
                max_second = max_first
                max_first = P[j]
            elif (P[j] > max_second):
                max_second = P[j]
            result += max_second
    else:
        continue

print(result)

Submission status: Time Limit Exceeded

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

res = 0
for li in range(N-1):
  first = max(P[li], P[li+1])
  second = min(P[li], P[li+1])
  for ri in range(li+1, N):
    if ri == li+1:
      res += second
    else:
      tmp = P[ri]
      if tmp > first:
        second = first
        first = tmp
      elif tmp > second:
        second = tmp
      res += second

print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
index=[]
for i in range(n):
    temp=p.index(i+1)+1
    index.append(temp)
ans=0
for i in range(n-1):
    top=max(p[i],p[i+1])
    sec=min(p[i],p[i+1])
    lis=[sec]
    ans+=sec
    for j in range(i+1,n):
        if(j==i+1):
            continue
        if(p[j]>top):
            sec=top
            top=p[j]
        elif(p[j]>sec):
            sec=p[j]
        ans+=sec
        lis.append(sec)
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
P=list(map(int, input().split()))
l=[]
for i in range(N):
    l.append([P[i],i+1])
l.sort(reverse=True)
a=0
p=[0,0,N+1,N+1]
for i in range(N):
    d=bisect.bisect_left(p,l[i][1])
    a+=((p[d-1]-p[d-2])*(p[d]-l[i][1])+(l[i][1]-p[d-1])*(p[d+1]-p[d]))*l[i][0]
    p.insert(d,l[i][1])
print(a)

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):
  if x[l] > x[l+1]:
    m = x[l]
    s = x[l+1]
  else:
    s = x[l]
    m = x[l+1]
  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:
# coding: utf-8
# Your code here!
n=int(input())
P=list(map(int,input().split()))
ans=0


for i in range(n-1):
    l=[]
    m=0
    sm=0
    l.append(P[i])
    for j in range(i+1,n):
        l.append(P[j])
        if m==0:
            m=max(l)
            sm=min(l)
        elif P[j]>sm:
            if P[j]>m:
                sm=m
                m=P[j]
            else:
                sm=P[j]
        ans+=sm

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
n=int(input())
p=list(map(int,input().split()))
d=[0]*n
for i in range(n):
    d[p[i]-1]=i
s=[-1,-1,d[i],n,n]
c=0
for i in range(n-2,-1,-1):
    g=bisect_left(s,d[i])
    c+=(i+1)*((s[g]-d[i])*(d[i]-s[g-2])+(s[g+1]-d[i])*(d[i]-s[g-1])-2*(s[g]-d[i])*(d[i]-s[g-1]))
    s.insert(g,d[i])
print(c)

Submission status: Time Limit Exceeded

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

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

print(sumX)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
b = list(map(int, input().split()))
sum = 0
for i in range(n):
  for j in range(i+1, n):
    c = sorted(b[i:j+1])
    if len(c) > 1:
      sum += c[-2]
    else:
      sum += c[-1]
print(sum)

Submission status: Time Limit Exceeded

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


count = 0
ans = 0
before_list = []
for i in range(N-1):
    a = min(l[i],l[i+1])
    b = max(l[i],l[i+1])
    before_list.append((a,b))
    ans = ans + a
##N回この作業をする
while(count < N-2):
    after_list = []
    for i in range(len(before_list)-1):
        a1 = before_list[i][0]
        a2 = before_list[i][1]
        b1 = before_list[i+1][0]
        b2 = before_list[i+1][1]
        if (a2 == b2) :
            a = max(a1,b1)
            b = b2
        else :
            a = min(a2,b2)
            b = max(a2,b2)
        after_list.append((a,b))
        ans = ans + a
    before_list = after_list
    count = count + 1
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):
  for j in range(i+1,n):
    P = p[i:j+1]
    P.sort(reverse=True)
    ans += P[1]
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n = int(input())
    p = list(map(int, input().split()))
    second = sorted(p)[-2]
    dp = [[[0, 0] for _ in range(n)] for __ in range(n)]
    ans = 0
    for i in range(n - 1):
        dp[i][i + 1][1], dp[i][i + 1][0] = sorted([p[i], p[i + 1]])
        ans += dp[i][i + 1][1]
        for j in range(i + 2, n):
            _, dp[i][j][1], dp[i][j][0] = sorted(
                [dp[i][j - 1][0], dp[i][j - 1][1], p[j]])
            ans += dp[i][j][1]
            if dp[i][j][1] == second:
                ans += dp[i][j][1] * (n - j - 1)
                break
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=[0]+[int(i) for i in input().split()]
#print(P)
num=0
for L in range(1,N):
  PL=P[L]
  Psec=0
  Pmax=PL
  for R in range(L+1,N+1):
    if Pmax<P[R]:
      Psec=Pmax
      Pmax=P[R]
    elif Psec<P[R]:
      Psec=P[R]
    num+=Psec
    #print(num,PL,Psec)
print(num)

Submission status: Time Limit Exceeded

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

for i,j in combinations(P,2):
  l,r = sorted([i,j])
  a+=sorted(P[l-1:r])[-2]

print(a)

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:
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])
    a,b,c,d,e = bis[inser-2:inser+3]
    foo = (e-d)*(c-b) + (d-c)*(b-a)
    ans += foo*(N-i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
P=np.array(list(map(int, input().split())))

sum_1=0
for i in range(N-1):
    for j in range(i+1,N):
        A=np.sort(P[i:j+1])[::-1]
        sum_1+=A[1]
print(sum_1)

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

def second_largest(numbers):
	count = 0
	m1 = m2 = float('-inf')
	for x in numbers:
		count += 1
		if x > m2:
			if x >= m1:
				m1, m2 = x, m1            
			else:
				m2 = x
	return m2 if count >= 2 else None

for i in range(0,n-1):
	for j in range(i+1,n):
		s=p[i:j+1]
		cnt+= second_largest(s)

		#s_s=sorted(s)
		#s_ss=s_s.pop()
		#cnt+=s_s[j-i-1]
print(cnt)

Submission status: Time Limit Exceeded

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

SUM = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    Pcopy = P
    Pcopy2 = Pcopy[i:j+1]
    Pcopy2.sort()
    SUM += Pcopy2[-2]

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
def second_max(p, s, e):
    lis = p[s:e+1]
    lis.remove(max(lis))
    return(max(lis))
num = int(input())
p = list(map(int, input().split()))
sum = 0
for i in range(num - 1):
    for j in range(i+1, num):
        sum += second_max(p, i, j)
print(sum)