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 heapq, copy

N = int(input())
P = list(map(int, input().split()))
P = list(map(lambda x : -1 * x, P))
# print(P)
ans = 0

for l in range(1, N):
	lst = []
	heapq.heappush(lst, P[l - 1])
	# print(lst)
	for r in range(l + 1, N + 1):
		heapq.heappush(lst, P[r - 1])
		max = heapq.heappop(lst)
		max_2 = heapq.heappop(lst)
		# print(max_2)
		ans += max_2
		heapq.heappush(lst, max)
		heapq.heappush(lst, max_2)

print(-1 * ans)

Submission status: Time Limit Exceeded

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

first = 0
second = 0
isum = 0

for l in range(n-1):
    for r in range(l+1,n):
        if r == l + 1:
            first = max(p[l],p[r])
            second = min(p[l],p[r])
            isum += second
            continue
        if p[r] > first:
            second = first
            first = p[r]
            isum += second
            continue
        if p[r] > second:
            second = p[r]
            isum += second
            continue
        isum += second

print(isum)

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(' ')
Ans = 0

for i in range(N):
  Data[i] = int(Tmp[i])
  if i > 0:
    for j in range(i):
      TmpData = Data[j:i+1]
      TmpData.sort(reverse=True)
      Ans += TmpData[1]


print(Ans)

Submission status: Time Limit Exceeded

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

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

print(sum(X))

Submission status: Time Limit Exceeded

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

L = 0
ans = 0

for i in range(0,N-1):
    for j in range(i+1,N):
        L = P[i:j+1]
        ans = ans + sorted(L)[-2]
            

print(ans)

Submission status: Time Limit Exceeded

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

def X(P,L,R):
    s = P[L-1:R]
    s.pop(s.index(max(s)))
    return max(s)

ans = 0
for L in range(1, N):
    for R in range(L+1, N+1):
        ans += X(P,L,R)
print(ans)

Submission status: Time Limit Exceeded

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

import itertools
a = list(itertools.combinations(range(0, N), 2))

dp = [[[None] for _ in range(N)] for _ in range(N)]

# def dpcheck(i, j):
#     if dp[i][j] is not None:
#         return dp[i][j]
#     target = P[a[i][0]:a[i][1]]
#     target.sort()
#     dp[i][j] = target
#     return target

all = 0
for i in range(len(a)):
    target = P[a[i][0]:a[i][1]+1]
    target.sort()
    all += target[-2]
print(all)

Submission status: Time Limit Exceeded

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

total=sorted(p)
totalfirst=total[len(p)-1]
totalsecond=total[len(p)-2]

totalfirstpoint=p.index(totalfirst)
totalsecondpoint=p.index(totalsecond)

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
  checked=False
  for j in range(i+2,n):
    if i<=totalfirstpoint and i<=totalsecondpoint and totalfirstpoint<=j and totalsecondpoint<=j:
      sum=sum+totalsecond
      if not checked:
        first=totalfirstpoint
        second=totalsecondpoint
        checked=True
    else:
      if p[j]>first:
        first,second=p[j],first
      elif p[j]>second:
        second=p[j]
      sum=sum+second

print(sum)

Submission status: Time Limit Exceeded

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

def find_second(p,s,e):
    max1=0
    pos1=0
    for i in range(s-1,e):
        if p[i]>max1:
            max1=p[i]
            pos1=i
    #print(pos1,max1)
    max2=0
    pos2=0
    for i in range(s-1,e):
        if p[i]>max2 and i!=pos1:
            max2=p[i]
            pos2=i
    #print(pos2,max2)
    return p[pos2]

ans=0
for j in range(1,n):
    for k in range(j+1,n+1):
        ans+=find_second(p,j,k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())
P=[int(x) for x in input().split()]
X=[-1 for i in range(N+1)]
for i in range(N):
    X[P[i]] = i
x1=X[N]
x2=X[N-1]
x1,x2=sorted([x1,x2])
i=x1+1
j=N-x2
ans=i*j*(N-1)
loc= [-1,-1,x1,x2,N,N]
for p in range(N-2,0,-1):
    x=X[p]
    ii=bisect.bisect(loc, x)
    tmp=loc[ii-2:ii+2]
    ans+=(tmp[2]-x)*(tmp[1]-tmp[0])*p
    ans+=(x-tmp[1])*(tmp[3]-tmp[2])*p
    #bisect.insort(loc,x)
    loc=loc[:ii]+[x]+loc[ii:]
print (ans)

Submission status: Time Limit Exceeded

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


class SegmentTree:
    def __init__(self, n, f, e):
        self.n = 2**((n - 1).bit_length())
        self.f = f
        self.e = e
        self.d = [e for _ in range(2 * self.n)]

    def __setitem__(self, key, value):
        key += self.n - 1
        self.d[key] = value
        while key > 1:
            key //= 2
            self.d[key] = self.f(self.d[2 * key], self.d[2 * key + 1])

    def __getitem__(self, key):
        return self.q(key, 1, 1, self.n + 1)

    def q(self, key, i, left, right):
        return (
            self.e if left >= key.stop or right <= key.start else
            self.d[i] if key.start <= left <= right <= key.stop else
            self.f(
                self.q(key, 2 * i, left, (left + right) // 2),
                self.q(key, 2 * i + 1, (left + right) // 2, right)
            )
        )


L = SegmentTree(N + 1, max, 0)
R = SegmentTree(N + 1, min, N + 1)
for i in range(N):
    R[P[i]] = i + 1
ans = 0
for i in range(1, N + 1):
    y = P[i - 1] + 1
    # 左が最大の場合
    k = L[y:(N + 1)]
    if k > 0:
        z = P[k - 1]
        j = max(L[y:z], L[(z + 1):(N + 1)])
        r = R[y:(N + 1)]
        ans += (k - j) * (r - i) * P[i - 1]
    # 右が最大の場合
    k = R[y:(N + 1)]
    if k <= N:
        z = P[k - 1]
        j = min(R[y:z], R[(z + 1):(N + 1)])
        l = L[y:(N + 1)]
        ans += (j - k) * (i - l) * P[i - 1]
    L[P[i - 1]] = i
    R[P[i - 1]] = N + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(i) for i in input().split()]
# P_dict = dict(zip([i for i in range(N)], P))

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
        if x == N - 1:
            counter += x * (N - r - 1)
            break
print(counter)

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(i+1,n):
        ans += sorted(p[i:j+1])[j-i-1]
print(ans)

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):
    if R == L + 1:
        s += min(islice(P, L - 1, R))
        continue
    ll = sorted(islice(P, L - 1, R), reverse=True)
    s += nth(ll, 1)
else:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	lpn = list(map(int, input().split()))
	
	ret=0
	a=[0 for _ in lpn]
	mv=-1
	for i,v in enumerate(lpn[-1::-1]):
		mv = max(v,mv)
		a[-1+-1*i]=mv
		
	#print(a)
		

	for i,l in enumerate(lpn[:-1]):
		fm = l
		sm=-1
		#print(fm)
		for j, r in enumerate(lpn[i+1:]):
			if r > sm:
				sm=r
			if sm > fm:
				fm,sm = sm,fm
				
			if a[i+1] < sm:
				ret += sm*(len(lpn)-j)
				break
			#print(i,fm,sm)
			ret+=sm
			
	print(ret)
	
	
#+++++


if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
A = [int(i) for i in input().split()]
sum = 0
max_num = 0
second_num=0
for i in range(1,num):
    max_num = A[num-i]
    for j in range(0,num-i):
        if(max_num < A[num-i-j-1]):
            second_num = max_num
            max_num = A[num-i-j-1]
        elif(second_num < A[num-i-j-1]):
            second_num = A[num-i-j-1]
        sum = sum + second_num
    max_num = 0
    second_num=0
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = tuple(map(int, input().split()))
change = n//2
pp = [0] * (n+1)
for i in range(n):
    pp[p[i]] = i


ans = 0
for i in range(change):
    target = p[i]
    a = -1
    b = -1
    c = n
    d = n
    flag = 0
    for j in range(i-1, -1, -1):
        if p[j] > target:
            b = j
            if b != 0:
                flag = 1
            break
    if flag == 1:
        for j in range(b-1, -1, -1):
            if p[j] > target:
                a = j
                break

    flag = 0
    for j in range(i+1, n):
        if p[j] > target:
            c = j
            if c != n-1:
                flag = 1
            break
    if flag == 1:
        for j in range(c+1, n):
            if p[j] > target:
                d = j
                break


    ans += (b-a)*(c-i)*target + (d-c)*(i-b)*target

for i in range(change, n):
    target = p[i]
    a = -1
    b = -1
    c = n
    d = n
    for j in range(target + 1, n + 1):
        x = pp[j]
        if x < i:
            if b < x:
                a = b
                b = x
            elif a < x:
                a = x
        if x > i:
            if x < c:
                d = c
                c = x
            elif x < d:
                d = x


    ans += (b-a)*(c-i)*target + (d-c)*(i-b)*target
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():

	input = sys.stdin.readline

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

	x = 0
	for L in range(N-1):
		first = P[L]
		second = 0
		for i in range(1,N-L):
			ind = L+i
			if P[ind]>first:
				second = first
				first = P[ind]
			elif P[ind]>second:
				second = P[ind]

			x = x+second

	print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [0] * n
cnt = 0
ans = 0

def check(x,y):
    max1 = 0
    max2 = 0

    for i in range(x,y):
        if i == x:
            max1 = p[i]
            continue
        if max1 < p[i]:
            max2 = max1
            max1 = p[i]
            dp[i] = max2
        elif max2 < p[i]:
            max2 = p[i]
            dp[i] = max2
        else:
            dp[i] = max2
        
check(0,n)
ans += sum(dp)

for i in range(1,n-1):
    cnt = 0
    temp = p[i-1]
    for j in range(i,n):
        if dp[i] == temp:
            cnt += 1
            continue
        else:
            check(i,n)
            ans += sum(dp[i+1:])
            break
    else:
        check(i,n)
        ans += sum(dp[i+1:])
            
print(ans)

Submission status: Time Limit Exceeded

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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = -1

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

res = 0
s = [0]*(n+1)

update(p[0],0)
for i in range(1,n):
    k1 = query(p[i],n+1)
    if k1 != -1:
        update(p[k1],-1)
        k2 = query(p[i],n+1)
        s[i] = p[i]*(k1-k2) + s[k1]
        res += s[i]
        update(p[k1],k1)
    update(p[i],i)


ide_ele = -n
seg=[ide_ele]*2*num

s = [0]*(n+1)

update(p[-1],1-n)
for i in range(n-2,-1,-1):
    k1 = query(p[i],n+1)
    if k1 != -n:
        update(p[-k1],-n)
        k2 = query(p[i],n+1)
        s[i] = p[i]*(k1-k2)+s[-k1]
        res += s[i]
        update(p[-k1],k1)
    update(p[i],-i)

print(res)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(int, input().split()))
X1=[[0 for _ in range(N)] for _ in range(N)]
X2=[[0 for _ in range(N)] for _ in range(N)]
for i in range(1, N):
  X1[i-1][i]=max(P[i-1], P[i])
  X2[i-1][i]=min(P[i-1], P[i])
for i in range(2, N):
  for L in range(N-1):
    for R in range(L+i, N-i+2):
      if P[R]>X1[L][R-1]:
        X1[L][R], X2[L][R]=P[R], X1[L][R-1]
      else:
        X1[L][R]=X1[L][R-1]
        if P[R]>X2[L][R-1]:
          X2[L][R]=P[R]
        else:
          X2[L][R]=X2[L][R-1]
res=0
for i in range(N):
  for j in range(i+1, N):
    res+=X2[i][j]
print(res)

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(N):
        S = P[i:j+1]
        if len(S) >= 2:
            ans += sorted(S)[-2]
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):
    count = 0
    m1 = m2 = float('-inf')
    for x in b[i:j+1]:
        count += 1
        if x > m2:
            if x >= m1:
                m1, m2 = x, m1            
            else:
                m2 = x
    sum += m2
print(sum)

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
now = N
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:
n = int(input())
p = tuple(map(int, input().split()))
change = (n//8)*7

pp = [0] * (n+1)
for i in range(n):
    pp[p[i]] = i


ans = 0
for i in range(change):
    target = p[i]
    a = -1
    b = -1
    c = n
    d = n
    flag = 0
    for j in range(i-1, -1, -1):
        if p[j] > target:
            b = j
            if b != 0:
                flag = 1
            break
    if flag == 1:
        for j in range(b-1, -1, -1):
            if p[j] > target:
                a = j
                break

    flag = 0
    for j in range(i+1, n):
        if p[j] > target:
            c = j
            if c != n-1:
                flag = 1
            break
    if flag == 1:
        for j in range(c+1, n):
            if p[j] > target:
                d = j
                break


    ans += (b-a)*(c-i)*target + (d-c)*(i-b)*target

for i in range(change, n):
    target = p[i]
    a = -1
    b = -1
    c = n
    d = n
    for j in range(target + 1, n + 1):
        x = pp[j]
        if x < i:
            if b < x:
                a = b
                b = x
            elif a < x:
                a = x
        if x > i:
            if x < c:
                d = c
                c = x
            elif x < d:
                d = x


    ans += (b-a)*(c-i)*target + (d-c)*(i-b)*target
print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N = int(input())
        P = list(map(int, input().split()))
        P.insert(0, 0)
        #print(P)
        
        Sum = 0
        for L in range(2, N+1):
            if P[L-1] > P[L]:
                maxi = P[L-1]
            else:
                maxi = P[L]
            
            if P[L-1] > P[L]:
                second = P[L]
            else:
                second = P[L-1]
            
            dp = [second]
            for R in range(L+1, N+1):
                if P[R] >= maxi:
                    second = maxi
                    maxi = P[R]
                else:
                    if P[R] > second:
                        second = P[R]
                dp.append(second)
            #print(dp)
            Sum += sum(dp)
        print(Sum)
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int,input().split()))
m = 0
for i in range(n-1):
    z = p[i:]
    z.remove(max(p[i:]))
    s = max(z)
    for j in range(i+1,n):
        t = p[i:j+1]
        t.remove(max(t))
        if max(t) == s:
            m += s*(n-j)
            break
        else:
            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(N):
    for j in range(N):
        S = sorted(P[i:j+1])
        if len(S) >= 2:
            ans += S[-2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = tuple(map(int, input().split()))
change = (n//4)*3

pp = [0] * (n+1)
for i in range(n):
    pp[p[i]] = i


ans = 0
for i in range(change):
    target = p[i]
    a = -1
    b = -1
    c = n
    d = n
    flag = 0
    for j in range(i-1, -1, -1):
        if p[j] > target:
            b = j
            if b != 0:
                flag = 1
            break
    if flag == 1:
        for j in range(b-1, -1, -1):
            if p[j] > target:
                a = j
                break

    flag = 0
    for j in range(i+1, n):
        if p[j] > target:
            c = j
            if c != n-1:
                flag = 1
            break
    if flag == 1:
        for j in range(c+1, n):
            if p[j] > target:
                d = j
                break


    ans += (b-a)*(c-i)*target + (d-c)*(i-b)*target

for i in range(change, n):
    target = p[i]
    a = -1
    b = -1
    c = n
    d = n
    for j in range(target + 1, n + 1):
        x = pp[j]
        if x < i:
            if b < x:
                a = b
                b = x
            elif a < x:
                a = x
        if x > i:
            if x < c:
                d = c
                c = x
            elif x < d:
                d = x


    ans += (b-a)*(c-i)*target + (d-c)*(i-b)*target
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n-1):
  for j in range(n-i-1):
    b = a[i:i+j+2]
    b.remove(max(b))
    ans += max(b)
print(ans)

Submission status: Time Limit Exceeded

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

L = 0
ans = 0

for i in range(N):
    for j in range(N):
        if i < j:
            L = P[i:j+1]
            ans = ans + sorted(L)[-2]
            

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

count = 0
for i in range(N-1):
    can_use = sorted(P[i:i+1])
    num = 0
    for j in range(i+1, N):
        if P[j] < num:
            count += num
            continue
        bisect.insort(can_use, P[j])
        can_use = can_use[-2:]
        num = can_use[-2]
        count += num

print(count)

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    resolve()

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(i + 1, n):
        if j == i + 1:
            first_max = max(p[i], p[i + 1])
            second_max = min(p[i], p[i + 1])
        else:
            if  p[j] > first_max:
                second_max = first_max
                first_max = p[j]
            elif p[j] > second_max:
                second_max = p[j]
        ans += second_max

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(i + 1, n):
        picked = sorted(p[i: j + 1])
        ans += picked[-2]
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-1):
    first = b[i]
    second = 0
    for j in range(i+1,n):
        if(second < b[j]):
            if(first < b[j]):
                second = first
                first = b[j]
            else:
                second = b[j]
        sum += second
print(sum)

Submission status: Time Limit Exceeded

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


ret = 0
for l in range(n - 1):
    second_max, max_ = sorted(pl[l:l+2])
    for r in range(l + 1, n):
        ret += sorted(pl[l:r+1])[-2]

print(ret)

Submission status: Time Limit Exceeded

Solution code:
#E

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

for l in range(1,n):
    for r in range(l+1,n+1):
        kari = sorted(p[l:(r+1)])[-2]
        ans += kari

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())  
P=list(map(int, input().split())) 
Xs = [np.sum([np.sort(P[L:R+1])[-2] for R in range(L+1, N)]) for L in range(N-1)]
print(np.sum(Xs))

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
    #migi
    m1 = 1
    m2 = 0
    f1 = True
    f2 = False
    k1 = True
    k2 = False
    for j in range(1,n+1):
        if i-j < 0:
            f1 = False
        if i+j > n-1:
            k1 = False
        if f1:
            if not f2:
                if p[i-j] < p[i]:
                    h1 += 1
                else:
                    h2 += 1
                    f2 = True
            else:
                if p[i-j] < p[i]:
                    h2 += 1
                else:
                    f1 = False
        if k1:
            if not k2:
                if p[i+j] < p[i]:
                    m1 += 1
                else:
                    m2 += 1
                    k2 = True
            else:
                if p[i+j] < p[i]:
                    m2 += 1
                else:
                    k1 = False
        if not k1 and not f1:
            break
    ans += p[i]*(h1*m2+m1*h2)

print(ans)

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):
        b, a = sorted([p[i], p[i + 1]])
        ans += b
        for j in range(i + 2, n):
            x = p[j]
            if x > a:
                a, b = x, a
            elif x > b:
                a, b = a, x
            else:
                a, b = a, b
            ans += b
            if b == second:
                ans += b * (n - j - 1)
                break
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import sys

input = sys.stdin.readline

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

pos = [[] for _ in range(n + 1)]
for ind, pp in enumerate(p):
    for j in range(pp + 1):
        pos[j].append(ind)

ans = 0
for i, pp in enumerate(p):
    ind = bisect_left(pos[pp], i)

    left = 1
    if ind - 1 >= 0:
        left = i - pos[pp][ind - 1]
    else:
        left = i + 1
    right = 0
    if ind + 1 < len(pos[pp]):
        i_right = pos[pp][ind + 1]
        right = 1
        if ind + 2 < len(pos[pp]):
            right = pos[pp][ind + 2] - i_right
        else:
            right = n - i_right

    # print(i, pp, left * right, left, right)
    ans += left * right * pp

    left = 0
    if ind - 1 >= 0:
        i_left = pos[pp][ind - 1]
        left = 1
        if ind - 2 >= 0:
            left = i_left - pos[pp][ind - 2]
        else:
            left = i_left + 1
    right = 1
    if ind + 1 < len(pos[pp]):
        right = pos[pp][ind + 1] - i
    else:
        right = n - i

    # print(i, pp, left * right, left, right)
    ans += left * right * pp

print(ans)

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 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()))
second_maxs = {}
tm = sm = fm = -1
ans = 0
for i, v1 in enumerate(P):
    for j, v2 in enumerate(P[i+1:], i+1):
        if j == i + 1:
            second_maxs[i, j] = (min(v1, v2), max(v1, v2))
        else:
            stmp, ftmp = second_maxs[i, j-1]
            if v2 > ftmp:
                second_maxs[i, j] = (ftmp, v2)
            else:
                if v2 > stmp:
                    second_maxs[i, j] = (v2, ftmp)
                else:
                    second_maxs[i, j] = (stmp, ftmp)
        ans += second_maxs[i, j][0]

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(2, N+1):
    for j in range(N+1-i):
        P_sort = P[j:j+i]
        X += sorted(P_sort)[-2]

print(X)

Submission status: Time Limit Exceeded

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

#dp = [0]*(n+1)
dp = [[0 for i in range(n+1)] for j in range(n+1)]

def getX(l, r):
    temp = p[l-1:r]
    temp.sort()
    if dp[l][r] > 0:
        return dp[l][r]
    else:
        dp[l][r] = temp[-2]
        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:
n = int(input())
pp = list(map(int, input().split()))


def sub(pp):
	m = len(pp)
	ans = 0
	for i in range(m - 1):
		for j in range(i + 1, m):
			#print(i, j)
			ans += sorted(pp[i:(j + 1)], reverse = True)[1]
	return ans

def calc(a, b):
	if b - a < 1:
		return 0
	elif b - a == 1:
		return min(pp[b], pp[a])
	else:
		pn = sorted(pp[a:(b + 1)], reverse = True)
		f = pp.index(pn[0])
		s = pp.index(pn[1])
		if f > s:
			ans = calc(a, f - 1) + calc(s + 1, b) - calc(s + 1, f - 1) + pp[s] * ((s - a + 1) * (b - f + 1))
		else:
			ans = calc(a, s - 1) + calc(f + 1, b) - calc(f + 1, s - 1) + pp[s] * ((f - a + 1) * (b - s + 1))
		#print(a, b, f, s,  ans)
		return ans


#print(sub(pp))
print(calc(0, n - 1))

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= b[i:j+1]
    c.remove(max(c))
    sum += max(c)
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

n = int(input())
#n, k = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
num = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
# s = [input() for i in range(n)]
#s = input()
# list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]
#s = [input() for i in range(n)]

a = [[0 for _ in range(n+1)] for _ in range(n+1)]
b = [[0 for _ in range(n+1)] for _ in range(n+1)]

kotae = 0

for i in range (2,n+1) :
    for j in range (0, n-i+1) :
        if (i == 2) :
            a[j][2] = max(num[j],num[j+1])
            b[j][2] = min(num[j],num[j+1])
            kotae += b[j][2]
        else :
            if(num[j+i-1] > b[j][i-1]) :
                a[j][i] = max(a[j][i-1],num[j+i-1])
                b[j][i] = min(a[j][i-1], num[j+i-1])
                kotae += b[j][i]
            else :
                a[j][i] = a[j][i-1]
                b[j][i] = b[j][i-1]
                kotae += b[j][i]

print(kotae)

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:
while True:
    try:
        N = int(input())
        P = list(map(int, input().split()))
        P.insert(0, 0)
        #print(P)
        
        Sum = 0
        for L in range(2, N+1):
            maxi = max(P[L-1], P[L])
            second = min(P[L-1], P[L])
            dp = [second]
            for R in range(L+1, N+1):
                if P[R] >= maxi:
                    second = maxi
                    maxi = P[R]
                else:
                    second = max(P[R], second)
                dp.append(second)
            #print(dp)
            Sum += sum(dp)
        print(Sum)
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import numpy as np
N = int(input())
P = np.array(input().split(),dtype=np.int32)
a = 0

for i,j in combinations(P,2):
  l,r = sorted([i,j])
  a+=np.sort(P[l-1:r],kind="quicksort")[-2]

print(a)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())
P=[int(x) for x in input().split()]
X=[-1 for i in range(N+1)]
for i in range(N):
    X[P[i]] = i
x1=X[N]
x2=X[N-1]
x1,x2=sorted([x1,x2])
i=x1+1
j=N-x2
ans=i*j*(N-1)
loc= [-1,-1,x1,x2,N,N]
for p in range(N-2,0,-1):
    x=X[p]
    ii=bisect.bisect(loc, x)
    tmp=loc[ii-2:ii+2]
    ans+=(tmp[2]-x)*(tmp[1]-tmp[0])*p
    ans+=(x-tmp[1])*(tmp[3]-tmp[2])*p
    bisect.insort(loc,x)
print (ans)