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:
n = int(input())
p = list(map(int, input().split()))
x = 0
for l in range(n - 1):
    for i in range(2, n - l + 1):
        if p[l] <= p[l + 1]:
            first = p[l + 1]
            second = p[l]
        else:
            first = p[l]
            second = p[l + 1]
        if i != 2:
            for k in range(1, i - 1):
                if p[l + k + 1] >= first:
                    second = first
                    first = p[l + k + 1]
                elif p[l + k + 1] > second:
                    second = p[l + k + 1]
            x += second
        else:
            x += second
print(int(x))

Submission status: Time Limit Exceeded

Solution code:
# E

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

def input_list(list_):
    P = list_
    if len(P)==1:
#         print("value:", P)
#         print(0)
        return 0
    if len(P)==2:
#         print("value:", P)
#         print(min(P))
        return min(P)

    P_tmp = P[0:2]
    P_tmp.sort(reverse=True)
    value = P_tmp[1]
#     print("value:", P_tmp)
#     print(value)
    for i in range(2, len(P)):
        P_tmp += [P[i]]
        P_tmp.sort(reverse=True)
        value += P_tmp[1]
#         print("value:", P_tmp)
#         print(P_tmp[1])

        P_tmp = P_tmp[0:2]
    return value

value2 = 0
for i in range(len(P)):
    value2 += input_list(P[i:])
#     print(value2)

print(value2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int,input().split()))
ans=0
x=1
for j in range(n-1):
  q=p
  for k in range(j+1,n):
    q=p
    q[j:k+1].sort(reverse=True)
    r=[0]*n
    for l in range(k+1-j):
      r[l]=q[j+l]
    r.sort(reverse=True)
    ans += r[1]
    #print(x,r[1],ans,r)
    x+=1
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
def main():

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

    index = [-1]*N
    for i in range(N):
        index[P[i]-1] = i


    q = [-1, -1, index[-1], N, N]
    ans = 0
    for i in range(N-1):
        ind = index[-2-i]
        insertion = bisect_left(q, ind)
        ans += ((q[insertion+1]-q[insertion])*(ind-q[insertion-1]) + (q[insertion]-ind)*(q[insertion-1]-q[insertion-2])) * (N-1-i)
        q.insert(insertion, ind)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if 2<=N and N<=10**5:
    if N == len(P):
        ans = 0


        for i in range(N-1):
            List = []
            List.append(int(P[i]))
            # print(i)
            for j in range(i+1, N):
                List.append(int(P[j]))
                tmp = sorted(List, reverse=True)
                ans += tmp[1]

        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
p = [int(i) for i in input().split()]

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        P = np.array(p[i:j+1])
        P.sort()
        ans += P[-2]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(x) for x in input().split()]
mat = [[0] * N for i in range(N)]
def second(P, l, r):
  if mat[l][r]:
    return mat[l][r]
  else:
    tP = P[l:r + 1]
    ret = sorted(tP)[-2]
    i1 = P.index(max(tP))
    i2 = P.index(ret)
    for l in range(l, min(i1,i2)+1):
      for r in range(max(i1,i2), r):
        mat[l][r] = ret
    return ret

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
result = 0
for i in range(N-1):
  for j in range(i+1,N):
    if j==i+1:
      result += min(P[i:j+1])
      second_n = min(P[i:j+1])
      max_n = max(P[i:j+1])
    else:
      if max_n<P[j]:
        result += max_n
        second_n = max_n
        max_n = P[j]
      elif second_n<P[j]:
        result += P[j]
        second_n = P[j]
      else:
        result += second_n

print(result)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect
N = int(input())
P = list(map(int,input().split()))
A = {}

for i in range(N):
    A[P[i]] = i

ans = 0
B = []
B.insert(bisect(B,A[N]),A[N])
B.insert(bisect(B,A[N-1]),A[N-1])
ans += (N-1)*(N-B[1])*(B[0]+1)
for i in range(N-2):
    K = N - i - 2
    I = bisect(B,A[K])
    if I == 0:
        ans += (N-i-2)*(B[1]-B[0])*(A[K]+1)
    elif I == i+2:
        ans += (N-i-2)*(N-A[K])*(B[-1]-B[-2])
    else:
        if I-2 >= 0:
            if I+1 <= i+1:
                ans += (N-i-2)*((B[I]-A[K])*(B[I-1]-B[I-2]) + (A[K]-B[I-1])*(B[I+1]-B[I]))
            else:
                ans += (N-i-2)*((B[I]-A[K])*(B[I-1]-B[I-2]) + (A[K]-B[I-1])*(N-B[I]))
        else:
            if I+1 <= i+1:
                ans += (N-i-2)*((B[I]-A[K])*(B[I-1]+1) + (A[K]-B[I-1])*(B[I+1]-B[I]))
            else:
                ans += (N-i-2)*((B[I]-A[K])*(B[I-1]+1) + (A[K]-B[I-1])*(N-B[I]))
    B.insert(I,A[K])
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

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

    ran = 0
    if C[int(len(C)/2)] < P[L]:
        ran = range(int(len(C)/2)+1)
    else:
        ran = range(int(len(C)/2)+1, len(C))

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

    for R in range(L+1, N):
        if C[int(len(C)/2)] < P[R]:
            ran = range(int(len(C)/2)+1)
        else:
            ran = range(int(len(C)/2)+1, len(C))

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

print(result)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
P = list(map(int,input().split()))
# N = 10**5
# P = [i+1 for i in range(N)]
P2 = [[p] for p in P]
# print(P2)
def max2(l1, l2):
    # print(l1,l2)
    it = list((sorted(set(l1+l2) )))
    # print(it)
    if len(it) == 1:
        return [it[0], 0]
    return [it[-1], it[-2]]

# print(max2([1,3],[2,4]))
# print(max2([1],[2]))

def sum2(t_l):
    s = 0
    for lli in t_l:
        s += sum(lli)
    return s

sm = 0
for n in range(N):
    sm += sum2(P2)
    li = []
    for i in range(1,N-n):
        li.append(max2(P2[i], P2[i-1]))
    P2 = li

for n in range(N):
    sm -= sum(P)
    li = []
    for i in range(1,N-n):
        li.append(max(P[i], P[i-1]))
    P = li
print(sm)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*p, = map(int, input().split())
count = 0
for i in range(0, n-1):
    for j in range(i+1, n):
        count += sorted(p[i:j+1])[-2]
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(i) for i in input().split()]
 
sum = 0
 
cache = []
first = max(P[N - 1], P[N - 2])
second = min(P[N - 1], P[N - 2])
cache.append([first, second])
 
sum += second
 
for i in range(2, N):
  next_cache = []
 
  L = N - i - 1
 
  first = max(P[L], P[L + 1])
  second = min(P[L], P[L + 1])
  next_cache.append([first, second])
 
  sum += second
 
  for p in cache:
    first = p[0]
    second = p[1]
    if p[0] <= P[L]:
      first = P[L]
      second = p[0]
    elif p[0] > P[L] and p[1] <= P[L]:
      second = P[L]
 
    sum += second
 
    next_cache.append([first, second])
  
  cache = next_cache
 
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))[::-1]


i=0
result=0

while i<n-1:
  maxV=max(a[i],a[i+1])
  temp=min(a[i],a[i+1])
  result+=temp
  j=i+2
  while j<n:
    if temp>a[j]:
      result+=temp
      #print(i,j)
    else:
      if a[j]>maxV:
        temp=maxV
        result+=temp
        maxV=a[j]
      else:
        temp=a[j]
        result+=temp
    #print(i,j,temp)
        
    j+=1
  
  i+=1
  
print(result)

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):
        R = N-1
        while R > L:
            A = np.array(P[L:R+1])
            ind2 = np.where(A==np.sort(A)[-2])
            ind1 = np.where(A==np.sort(A)[-1])
            ind2 = int(ind2[0])
            ind1 = int(ind1[0])
            ind = max(ind1,ind2)
            ans += A[ind2]*(len(A)-ind)
            R = L + ind -1
                #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()))
L = [0]*N


for i in range(N):
    L[N-(P[i])]=i

total = 0
for i in range(N):
    for j in range(i+1,N):

        flag=0
        #print(i+1,j+1)
        for k in range(N):
            if((L[k]>=i)&(L[k]<=j)):
                flag+=1
            if(flag==2):
                total+=(N-k)
                break
print(total)

Submission status: Time Limit Exceeded

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

out = 0
first = 0
second = 0

for i in range(N-1):
#     print(i, out)
    first = max(P[i], P[i+1])
    second = min(P[i], P[i+1])
    out += second
    for j in range(i+2, N):
        first_tmp = max(first, second, P[j])
        second_tmp = sorted([first, second, P[j]])[-2]
        first = first_tmp
        second = second_tmp
        out += second

print(out)

Submission status: Time Limit Exceeded

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

index = [-1]*N
for i in range(N):
    index[P[i]-1] = i


q = [-1, -1, index[-1], N, N]
ans = 0
for i in range(N-1):
    ind = index[-2-i]
    insertion = bisect_left(q, ind)
    ans += ((q[insertion+1]-q[insertion])*(ind-q[insertion-1]) + (q[insertion]-ind)*(q[insertion-1]-q[insertion-2])) * (N-1-i)
    q.insert(insertion, ind)

print(ans)

Submission status: Time Limit Exceeded

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

class segMax:
  inf = 0
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最大値
    return max(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

class segMin:
  inf = 10 ** 10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = segMax(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  #print(ans)
  t = D[i]
  ma = TMa.getV(0, t)
  if ma == 0:
    ma = N + 1
    ma2 = N + 1
  else:
    ma2 = TMa.getV(0, ma - 1)

  mi = TMi.getV(t, N + 1)
  if mi == 10 ** 10:
    mi = 0
    mi2 = 0
  else:
    mi2 = TMi.getV(mi + 1, N + 1)
  
  if ma2 == 0: ma2 = N + 1
  if mi2 == 10 ** 10: mi2 = 0
  TMa.update(t, t)
  TMi.update(t, t)
  #print(ma2, ma, t, mi, mi2)
  if ma == N + 1 and mi == 0:
    continue
  if ma == N + 1:
    if mi2 != 0:
      ans += t * (mi2 - mi) * i
    else:
      ans += t * (N - mi + 1) * i
    continue
  if mi == 0:
    if ma2 != N + 1:
      ans += (N - t + 1) * (ma - ma2) * i
    else:
      ans += (N - t + 1) * (ma) * i
    continue
  if mi2 != 0:
    ans += (mi2 -  mi) * (t - ma) * i
    if ma2 != N + 1:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
  else:
    ans += (N - mi + 1) * (t - ma) * i
    if ma2 != N + 1:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
      

print(ans)

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):
    maxV = 0
    for r in range(l+1, n+1):
        if p[r-1] > maxV:
            ans += getX(l, r)
            prev = getX(l, r)
        else:
            ans += prev

print(ans)

Submission status: Time Limit Exceeded

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

import functools

@functools.lru_cache(maxsize=None)
def x(start, end):
    if start + 1 == end:
        return min(p[start-1], p[end-1]), max(p[start-1], p[end-1])
    if start + 2 == end:
        var1 = p[start-1]
        var2 = p[start]
        var3 = p[start+1]
        if var1 > var2 > var3:
            return var2, var1
        if var1 > var3 > var2:
            return var3, var1
        if var2 > var1 > var3:
            return var1, var2
        if var2 > var3 > var1:
            return var3, var2
        if var3 > var1 > var2:
            return var1, var3
        if var3 > var2 > var1:
            return var2, var3
    head, m = x(start, end-1)
    tail = p[end - 1]
    if tail < head:
        return head, m
    elif m > tail:
        return tail, m
    else:
        return m, tail

total = 0
for i in range(1, n):
    for j in range(i+1, n+1):
        target, _ = x(i, j)
        total += target
print(total)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
result = 0
for i in range(N-1):
  for j in range(i+1,N):
    result += sorted(P[i:j+1])[-2]
print(result)

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(int,input().split()))
sum=0
for L in range(1,N):
    for R in range(L+1,N+1):
        new_P=[]
        new_P.extend(P[L-1:R])
        new_P.sort(reverse=True)
        sum+=new_P[1]

print(sum)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# abc140/abc140_e
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    P = i2nn()
    r = 0
    for L in range(N-1):
        fst = P[L]
        sec = 0
        #print(fst, sec)
        #r2 = 0
        for R in range(L+1, N):
            p = P[R]
            #print(fst, sec, p, sorted((fst, sec, p))[1])
            if p > fst:
                sec = fst
                fst = p
            elif p > sec:
                sec = p
            r += sec
            #r2 += sec
        #print(r2)
    print(r)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
x = 0
for l in range(n - 1):
    for i in range(2, n - l + 1):
        if p[l] <= p[l + 1]:
            first = p[l + 1]
            second = p[l]
        else:
            first = p[l]
            second = p[l + 1]
        if i != 2:
            for k in range(1, i - 1):
                if p[l + k + 1] >= first:
                    second = first
                    first = p[l + k + 1]
                elif p[l + k + 1] > second:
                    second = p[l + k + 1]
            x += second
        else:
            x += second
print(int(x))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    p_s = LI()
    indexs = [0 for i in range(n+1)]
    for i in range(n):
        indexs[p_s[i]] = i
    A = [-1, -1, n, n]
    ans = 0
    for i in range(n):
        ind = indexs[n - i]
        index = bisect.bisect_right(A, ind)
        bisect.insort(A, ind)

        ans += (A[index-1] - A[index-2]) * (A[index+1] - A[index]) * (n-i)

        ans += (A[index+2] - A[index+1]) * (A[index] - A[index-1]) * (n-i)

    print(ans)

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):
    m1 = n1 = 0
    m2 = n2 = -1
    j0 = 0
    for j in range(i - 1, -1, -1):
        if P[j] < P[i]:
            m1 += 1
        else:
            m2 = 0
            j0 = j
            break
    for j in range(j0 - 1, -1, -1):
        if P[j] < P[i]:
            m2 += 1
        else:
            break
    j0 = N
    for j in range(i + 1, N):
        if P[j] < P[i]:
            n1 += 1
        else:
            n2 = 0
            j0 = j
            break
    for j in range(j0 + 1, N):
        if P[j] < P[i]:
            n2 += 1
        else:
            break
    ans += P[i] * ((m2 + 1) * (n1 + 1) + (m1 + 1) * (n2 + 1))
print(ans)

Submission status: Time Limit Exceeded

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

result = 0
for i in range(n):
     max = list[i]
     max2 = -1
     for j in range(i+1, n):
          if list[j] > max:
               if max > max2:
                    max2 = max
               max = list[j]
          else:
               if max2 < list[j]:
                    max2 = list[j]
          result += max2
print(result)

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[i:j+1]
    target.sort()
    dp[i][j] = target
    return target

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect

def solve():
    N = int(input())
    P = [int(p) for p in input().split()]
    appeared = []
    pindex = dict()
    for i in range(N):pindex[P[i]] = i
    appeared.append(-1)
    appeared.append(pindex[N])
    appeared.append(N)
    #print(pindex)

    total = 0
    for i in reversed(range(1, N)):
        #print(appeared)
        mid = bisect(appeared, pindex[i])
        #print(mid)
        if pindex[i] == 0:
            total += i * (appeared[2] - appeared[1])
        elif pindex[i] == N - 1:
            total += i * (appeared[N - i] - appeared[N - i - 1])
        else:
            if mid == 1: total += i * (appeared[2] - appeared[1]) * (pindex[i] + 1)
            elif mid == N + 1 - i: total += i * (appeared[mid - 1] - appeared[mid - 2]) * (N - pindex[i])
            else: 
                total += i * ((appeared[mid - 1] - appeared[mid - 2]) * (appeared[mid] - pindex[i]))
                total += i * ((pindex[i] - appeared[mid-1]) * (appeared[mid+1] - appeared[mid]))
        appeared.insert(mid, pindex[i])
 
        #print(total)

    print(total)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import functools

@functools.lru_cache(maxsize=None)
def x(start, end):
    if start + 1 == end:
        return min(p[start-1], p[end-1]), max(p[start-1], p[end-1])
    if start + 2 == end:
        var1 = p[start-1]
        var2 = p[start]
        var3 = p[start+1]
        l = sorted([var1, var2, var3])
        return l[1], l[2]
    head, m = x(start, end-1)
    tail = p[end - 1]
    if tail < head:
        return head, m
    elif m > tail:
        return tail, m
    else:
        return m, tail

total = 0
for i in range(1, n):
    for j in range(i+1, n+1):
        target, _ = x(i, j)
        total += target

print(total)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if 2<=N and N<=10**5:
    if N == len(P):
        ans = 0
        for i in range(N-1):
            # print()
            # print(i+1)
            for j in range(i+1, N):
                # print(j+1)

                # print()
                tmp = []
                for k in range(i, j+1):
                    tmp.append(int(P[k]))
                
                tmp.sort(reverse=True)
                ans += tmp[1]
                # print(tmp)
        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):
    max1 = max(p[i:(i+2)])
    max2 = min(p[i:(i+2)])
    ans += max2
    for j in range((n-i)-2):
        new = p[i+j+2]
        if max1 < new:
            max2 = max1
            max1 = new
        elif max2 < new:
            max2 = new
        ans += max2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def get_list(str):
    str_list = str.split(" ")
    result_list = []
    for str in str_list:
        result_list.append(int(str))
    return result_list

n = int(input())
num_str = input()
num_list = get_list(num_str)

result = 0
max_num = 0
second_num = 0

for n in num_list:
    if n > max_num:
        second_num = max_num
        max_num = n
    elif n > second_num:
        second_num = n
    result += second_num

while True:
    max_num = 0
    second_num = 0
    num_list.pop(0)
    if len(num_list) < 2:
        break
    num_list = list(reversed(num_list))
    for n in num_list:
        if n > max_num:
            second_num = max_num
            max_num = n
        elif n > second_num:
            second_num = n
        result += second_num

print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

count = 0
second = sorted(P)[-2]
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]
        if num == second:
            count += num * (N-j)
            break
        count += num

print(count)

Submission status: Time Limit Exceeded

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

def X(P,L,R):
    s = sorted(P[L-1:R])
    return s[-2]

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=input()
p=p.split()
p=list(map(int,p))
sum=0
for i in range(n-1):
    maxi=max(p[i],p[i+1])
    next_max=min(p[i],p[i+1])
   
    for j in range(i+1,n):
        if(p[j]>next_max and p[j]>maxi):
            next_max=maxi
            maxi=p[j]
            
            
        elif(p[j]<maxi and p[j]>next_max):
            next_max=p[j]
        sum+=next_max
        
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import heapq

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

print(sum(heapq.nlargest(2,P[i:j+1])[1] for i,j in itertools.combinations(range(N), 2)))

Submission status: Time Limit Exceeded

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

def nibanme(l):
    if len(l)>1:
        l[l.index(max(l))]*=-1
        return max(l)
    else:
        return 0
    
for i in range(int(N/2)):
    for j in range(1, len(p)):
        a=p[:j+1]
        b=p[j:]
        s+=nibanme(a)
        s+=nibanme(b)
    p.pop(0)
    p.pop(-1)
print(s)

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):
        ans = ans+ sorted(P[i:j+1])[-2]
                   

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=[int(x) for x in input().split()]
m=[0]*3
s=0
# largest: m[2], 2nd largest: m[1]
for L in range(0,n-1):
    m[0] = p[L]
    m[1] = 0
    for R in range(L+1, n):
        if p[R] > m[0]:
            m[1] = m[0]
            m[0] = p[R]
        elif p[R] > m[1]:
            m[1] = p[R]
        s += m[1]
print(s)

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 L != 0:
        if P[L-1] < P[L] and P[L-1] < P[L+1]:
            ans += temp
            temp -= P[L]
            continue
    if P[L] > P[L+1]: No1, No2 = P[L], P[L+1]
    else:   No1, No2 = P[L+1], P[L]
    ans += No2
 
    temp = 0
    for R in range(L+2, N):
        if P[R] > No1:  No1, No2 = P[R], No1
        elif P[R] > No2:    No2 = P[R]
        temp += No2
        ans += No2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calcXLR(numList,L,R):
    newList = []
    for i in range(L,R+1):
        newList.append(int(numList[i]))
    newList.remove(max(newList))
    return(max(newList))

num = int(input())
nums = input()
numList = []
numList = nums.split(" ")
output = 0

if num > 1 and num < (100001):
    for R in range(num):
        for L in range(R):
            if L < R:
                output = output + calcXLR(numList,L,R)
    print(output)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect

def solve():
    N = int(input())
    P = [int(p) for p in input().split()]
    appeared = []
    pindex = dict()
    for i in range(N):pindex[P[i]] = i
    appeared.append(-1)
    appeared.append(pindex[N])
    appeared.append(N)
    #print(pindex)

    total = 0
    for i in reversed(range(1, N)):
        #print(appeared)
        mid = bisect(appeared, pindex[i])
        #print(mid)
        if pindex[i] == 0:
            total += i * (appeared[2] - appeared[1])
        elif pindex[i] == N - 1:
            total += i * (appeared[N - i] - appeared[N - i - 1])
        else:
            if mid == 1: total += i * (appeared[2] - appeared[1]) * (pindex[i] + 1)
            elif mid == N + 1 - i: total += i * (appeared[mid - 1] - appeared[mid - 2]) * (N - pindex[i])
            else: 
                total += i * ((appeared[mid - 1] - appeared[mid - 2]) * (appeared[mid] - pindex[i]))
                total += i * ((pindex[i] - appeared[mid-1]) * (appeared[mid+1] - appeared[mid]))
        appeared.append(pindex[i])
        appeared.sort()
        #print(total)

    print(total)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

sums = 0
now_max=-10**6
now_add = 0
for i in range(N-1):
    now_max=max(P[i], P[i+1])
    now_add=min(P[i], P[i+1])
    
    for j in range(i+1,N):
        # secondが更新されなければ
        if now_add > P[j]:
            sums += now_add            
        elif now_max < P[j]:
            now_add = now_max
            now_max = P[j]
            sums += now_add            
        elif now_max > P[j] > now_add:
            now_add=P[j]
            sums += now_add
        else:
            sums += now_add


print(sums)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from bisect import insort
import copy

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):
    insort(ll, p[i+1])
    lll.append(copy.copy(ll))
    ans += lll[i][i]


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(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int,input().split()))
sum = 0
for l in range(0,n-1):
    for r in range(l+1,n):
        ld = p[l:r+1]
        ld.sort(reverse=True)
        sum += ld[1]
print(sum)

Submission status: Time Limit Exceeded

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


ans = 0
for i in range(n):
    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

print(ans)