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()))
dp = [[None]*(n+1) for _ in range(n)]
ans = 0

for i in range(n-1):
    for j in range(i+1, n):
        if i+1 == j:
            a, b = p[i], p[j]
            if a > b: a ,b = b, a
            dp[i][j] = (a, b)
            ans += a
        else:
            c = p[j]
            if dp[i][j-1][0] < c:
                if dp[i][j-1][1] < c:
                    dp[i][j] = (dp[i][j-1][1], c)
                else:
                    dp[i][j] = (c, dp[i][j-1][1], c)
            else:
                dp[i][j] = dp[i][j-1]
            ans += dp[i][j][0]

print(ans)

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': first, 'second': 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': first, 'second': second})

  sum += second

  for p in cache:
    first = p['first']
    second = p['second']
    if p['first'] <= P[L]:
      first = P[L]
      second = p['first']
    elif p['first'] > P[L] and p['second'] <= P[L]:
      second = P[L]

    sum += second

    next_cache.append({'first': first, 'second': second})
  
  cache = next_cache

print(sum)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
p=list(map(int,input().split()))
X=0
for i in range(N-1):
    x1=max(p[i],p[i+1])
    x2=min(p[i],p[i+1])
    X=X+x2
    for j in range(i+2,N):
        x=p[j]
        if(x2<x):
            if(x1<x):
                x2=x1
                x1=x
                X=X+x2
            else:
                x2=x
                X=X+x2
        else:
            X=X+x2
print(X)

Submission status: Time Limit Exceeded

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

total = 0
for l in range(0, n - 1):
    for r in range(l + 1, n):
        if l + 1 == r:
            if P[l] <= P[r]:
                top1, top2 = P[r], P[l]
            else:
                top1, top2 = P[l], P[r]
            total += top2
        else:
            if top1 <= P[r]:
                top2 = top1
                top1 = P[r]
            elif top2 <= P[r] < top1:
                top2 = P[r]
            else:
                pass
            total += top2
print(total)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n-1):
    m1,m2=max(p[i],p[i+1]),min(p[i],p[i+1])
    ans+=m2
    for j in range(i+2,n):
        buf=p[j]
        if m1<=buf:
            m1,m2=buf,m1
        elif m2<buf:
            m2=buf
        ans+=m2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np


def main():
    N = int(input())
    arr = np.array(input().split(), dtype='int64')

    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            ans += np.sort(np.unique(arr[i:j+1]))[-2]
       
    print(ans)







if __name__ =='__main__':
    main()

Submission status: Time Limit Exceeded

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

# def scnd(a,b):
# 	return sorted(P[a-1:b])[-2]

# print(scnd(1,3))

sm = 0

for l in range(1,N+1):
	# tmp1 = P[l-1:]
	# mxtmp1 = max(tmp1)
	# mxind1 = tmp1.index(mxtmp1)
	for r in range(l+1,N+1):
		tmp = P[l-1:r]
		mxtmp = max(tmp)
		mxind = tmp.index(mxtmp)
		del tmp[mxind]
		sm += max(tmp)

print(sm)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(len(p)-1):
    a, b = p[i], p[i+1]
    for j in range(i+2, len(p)):
        ans += min(a, b)
        l = sorted([a, b, p[j]])
        a, b = l[-1], l[-2]
    ans += min(a,b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

def fill_max(l, r):
    max_table[(l, r)] = max(max_table[(l, r - 1)], P[r])

def fill_X(l, r):
    if(max_table[(l, r-1)] < P[r]):
        X_table[(l, r)] = max_table[(l, r-1)]
    elif(P[r] < X_table[(l, r-1)]):
        X_table[(l, r)] = X_table[(l,  r-1)]
    else:
        X_table[(l, r)] = P[r]

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

max_table = collections.Counter()
X_table = collections.Counter()

ans = 0
for l in range(N-1):
    max_table[(l, l+1)] = max(P[l], P[l+1])
    X_table[(l, l+1)] = min(P[l], P[l+1])
    ans += X_table[(l, l+1)]
    for r in range(l+2, N):
        fill_max(l, r)
        fill_X(l, r)
        ans += X_table[(l, r)]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    p = list(map(int,input().split()))
    f=0
    s=0
    ans=0
    for i in range(n-1):
        for j in range(n-i-1):
            j+=i+1
            for k in range(j-i+1):
                if(s==(n-1)):
                    break
                if(p[i+k]>f):
                    s=f
                    f=p[i+k]
                elif(p[i+k]>s):
                    s=p[i+k]
            ans+=s
            f=0
            s=0
    print(ans)    
main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
sum = 0
max = 0
sub_max = 0
for i in range(n):
    max = p[i]
    sub_max = 0
    for j in range(i+1, n):
        if(p[j] >= max):
            sub_max = max
            max = p[j]
        elif(p[j] > sub_max):
            sub_max = p[j]
        sum += sub_max
print(sum)

Submission status: Time Limit Exceeded

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

top3 = []
summ = 0
for L in range(1, N):
    top3 = [P[L-1]]
    for R in range(L+1, N+1):
        #print("LR", L, R)

        top3.append(P[R-1])
        top3.sort()
        XLR = top3[-2]
        summ += XLR
        #print("XLR", XLR)
        top3 = top3[-2:]
        #print("top3", top3)
    try:
        top3.remove(P[L-1])
    except ValueError:
        pass

print(summ)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

from math import *
import os
import sys

#import scipy.optimize
import numpy as np


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

    ans = 0
    for L in range(N-1):
        for R in np.arange(L+1,N,1):
                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()))

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

ans += min(p[-2], p[-1])

print(ans)

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):
  first=max(p[i],p[i+1])
  second=min(p[i],p[i+1])
  sum=sum+second
  for j in range(i+2,n):
    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=[int(i) for i in input().split()]

dp_max=[[0 for i in range(N)] for j in range(N)]
dp_second=[[0 for i in range(N)] for j in range(N)]

for i in range(N-1):
    dp_max[i][i+1]=max(P[i],P[i+1])
    dp_second[i][i+1]=min(P[i],P[i+1])
    for j in range(i+2,N):
        if P[j]>dp_max[i][j-1]:
            dp_max[i][j]=P[j]
            dp_second[i][j]=dp_max[i][j-1]
        elif P[j]>dp_second[i][j-1]:
            dp_max[i][j]=dp_max[i][j-1]
            dp_second[i][j]=P[j]
        else:
            dp_max[i][j]=dp_max[i][j-1]
            dp_second[i][j]=dp_second[i][j-1]

ans=0
for i in range(N):
    for j in range(N):
        ans+=dp_second[i][j]

print(ans)

Submission status: Time Limit Exceeded

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

l = 0
r = 1
TempList = []
xlr = 0
while (l < n - 1):
	while (r < n):
		TempList = ListP[l : r + 1]
		TempList.remove(max(TempList))
		xlr += max(TempList)
		r += 1
	l += 1
	r = l + 1
print(xlr)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

place = [-1] * (N + 1)
for i in range(N):
    p = P[i]
    place[p] = i

ans = 0
big_place = [place[N]]
for i in range(N - 1, 0, -1):
    pos = bisect.bisect_left(big_place, place[i])
    if pos < len(big_place):
        right = big_place[pos]
    else:
        right = N
    if pos + 1 < len(big_place):
        right2 = big_place[pos + 1]
    else:
        right2 = N
    if pos - 1 >= 0:
        left = big_place[pos - 1]
    else:
        left = -1
    if pos - 2 >= 0:
        left2 = big_place[pos - 2]
    else:
        left2 = -1

    if left >= 0:
        left_cand = left - left2
    else:
        left_cand = 0
    right_cand = right - place[i]

    ans += i * left_cand * right_cand

    if right < N:
        right_cand = right2 - right
    else:
        right_cand = 0
    left_cand = place[i] - left
    ans += i * left_cand * right_cand

    big_place1 = big_place[:pos]
    big_place2 = big_place[pos:]
    big_place = big_place1 + [place[i]] + big_place2

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l2 = []
def second_largest(numbers):
    m1, m2 = 0, 0
    for x in numbers:
        if x >= m1:
            m1, m2 = x, m1
        elif x > m2:
            m2 = x
    return m2
for i in range(0,n-1):
    for j in range(1,n):
        l2.append(second_largest(l[i:j+1]))
print(sum(l2))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
P = list(map(int, input().split()))
# print(N, P)
ans = 0
l = []
for i in range(N - 1):
    bisect.insort(l, P[i])
    for j in range(i + 1, N):
        bisect.insort(l, P[j])
        # print(i, j, l)
        ans += l[-2]
    l = []
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
ans=0
for width in range(1,n):
    for i in range(n-width):
        tmp=p[i:i+width+1]
        # print(tmp)
        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 l in range(n-1):
    for r in range(l+1,n):
        ans+=sorted(p[l:r+1])[-2]
print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for i in range(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())
ps=list(map(int,input().split()))
ans=0

for i in range(n):
    first=0
    second=0
    for j in range(i,n):
        if first<ps[j]:
            second=0
            second+=first
            first=ps[j]
        elif second<ps[j]:
            second=ps[j]
        ans+=second

print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
A = [int(i) for i in input().split()]
sum = 0
for i in range(1,num):
    for j in range(0,i):
        B = A[j:i+1]
        B.sort(reverse=True)
        sum = sum + B[1]
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = list(map(int, input().split(" ")))
cnt = 0
for i in range(N-1):
  max = c[i]
  sub = 0
  for j in range(i+1,N):
    if max<=c[j]:
      
      sub = max
      max = c[j]
    elif sub<=c[j]:
      #print(c[j])
      sub = c[j]
    cnt += sub
    #print(sub)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
P = list(map(int, input().split()))# N
count = 0
    
for i in range(N):
  p = N
  while p >= i + 2:
    first = P[i:p]
    count += sorted(first)[-2]
    p -= 1
  
print(count)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  import sys
  import math

  sys.setrecursionlimit(10**7)
  readline=sys.stdin.readline

  n = int(input())
  p = list(map(int,input().split()))
  
  m = [0]*n
  
  ans = 0
  for l in range(n-1):
    a,b=max(p[l],p[l+1]),min(p[l],p[l+1])
    ans += b
    for r in range(l+2,n):
      if p[r]>a:
        a,b=p[r],a
      elif p[r]>b:
        b=p[r]
      ans += b
   
  print(ans)


if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

Solution code:

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

ret=0

ma = max(p[:2])
se = min(p[:2])


for l in range(n):
  for r in range(l,n):
    tmp = p[l:r]
    if len(tmp)<1:
      ma = max(p[l:l+2])
      se = min(p[l:l+2])
      #print("hei",ma, se)
      continue
    #print(tmp, end="")
    
    if p[r] > ma:
      se = ma
      ma = p[r]
    elif ma> p[r] and p[r] > se:
      se = p[r]
    
    #print(se)
    ret += se
    
print(ret)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
p = list(map(int, input().split()))
sum = 0
for L in range(1,n):
  for R in range(L+1,n+1):
    max = 0
    second = 0
    for i in range(L-1,R):
      if p[i] > max:
        second = max
        max = p[i]
      elif p[i] > second:
        second = p[i]
    sum += second

print(sum)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n = int(input())
    p = list(map(int, input().split()))
    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]
    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):
    fir = P[i]
    sec = 0
    for j in range(i+1, N):
        if fir < P[j]:
            sec = fir
            fir = P[j]
        elif sec < P[j]:
            sec = P[j]
        ans += sec
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

# 大きい数から挿入していく
# 左隣にあるインデックスを取得できるようにしておく
# そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ

def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
    i = 0
    s = 0
    step = 1<<(N.bit_length()-1)
    while step:
        if i+step <= N and s + tree[i+step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i+1

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) # 左にある既に書き込んだ数の個数
    BIT_add(c)
    R = N-x-L # 右にある既に書き込んだ数の個数
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。(a,b) と(c,d)が自由
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)

Submission status: Time Limit Exceeded

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

#print(N,P)

sum=0

for L in range(N-1):
  X=min(P[L],P[L+1])
  Y=max(P[L],P[L+1])
  sum=sum+X
  #print(X,Y)
  for R in range(L+2,N):
    if X >=P[R]:
     sum=sum+X
     #print(X,Y)
    else:
     X=min(Y,P[R])
     Y=max(Y,P[R])
     sum=sum +X
     #print(X,Y)
    
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
P = list(map(int, input().split()))
# print(N, P)
ans = 0
hq = []
for i in range(N - 1):
    heapq.heappush(hq, -P[i])
    for j in range(i + 1, N):
        # print('before', i, j, hq)
        heapq.heappush(hq, -P[j])
        a = heapq.heappop(hq)
        b = heapq.heappop(hq)
        ans -= b
        heapq.heappush(hq, a)
        heapq.heappush(hq, b)
        # print('after', i, j, hq)
    hq = []
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N = [int(s) for s in raw_input().split(" ")][0]
P = [int(s) for s in raw_input().split(" ")]
res = 0

for i in xrange(N-1):
    maxs, second = max(P[i], P[i+1]), min(P[i], P[i+1])
    res += second
    for j in xrange(i+2, N):
        if P[j] > maxs:
            maxs, second = P[j], maxs
        elif P[j] > second:
            second = P[j]
        res += second

print(res)

Submission status: Time Limit Exceeded

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

def set_2(a,b):
    if a > b:
        return a,b
    else:
        return b,a

d1 = 0
d2 = 0
ans = 0
for l in range(0,n-1):
    for r in range(l+1,n):

        if r - l == 1:
            d1,d2 = set_2(p[l],p[r])
            ans += d2
        else:
            if p[r] > d1:
                ans += d1
                d2 = d1
                d1 = p[r]
            elif p[r] <= d1 and p[r] > d2:
                ans += p[r]
                d2 = p[r]
            else:
                ans += d2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def scnd(a,b):
	return sorted(P[a-1:b])[-2]

# print(scnd(1,3))

sm = 0

for l in range(1,N+1):
	for r in range(l+1,N+1):
		sm += scnd(l,r)

print(sm)

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
s = 0
for i in range(n - 1):
    a = max(p[i], p[i + 1])
    b = min(p[i], p[i + 1])
    s += b
    for j in range(i + 2, n):
        if a >= p[j]:
            b = max(b, p[j])
        else:
            a, b = p[j], a
        s += b
print(s)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    ans = 0
    for x, y in itertools.combinations(range(N),2):
        ans += sorted(P[x:y+1])[-2]
    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-1):
    for j in range(i+1,n):
        ans += sorted(p[i:j+1])[-2]
print(ans)

Submission status: Time Limit Exceeded

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

N += 1
data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

E = [(v, i) for i, v in enumerate(P)]
E.sort(reverse=1)

add(1, 1)
add(N+1, 1)

ans = 0
for v, i in E:
    k = get(i+2)
    l1 = lower_bound(k-2)
    l0 = lower_bound(k-1)
    r0 = lower_bound(k)
    r1 = lower_bound(k+1)
    if l0 > 1:
        ans += (l0-l1) * (r0 - (i+2)) * v
    if r0 < N+2:
        ans += (r1-r0) * (i+2 - l0) * v
    add(i+2, 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-1):
    for j in range(i+1, n):
        a = p[i:j+1]
        a.sort(reverse=True)
        ans+=a[1]
print(ans)

Submission status: Time Limit Exceeded

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

def ncr(n,r,N,P,ans=[],result=[]):
    for i in range(len(n)):
        ans1=ans[:]
        ans1.append(n[i])
        n1=n[(i+1):]
        if len(ans1)==r:
            #print(ans1)
            buf = sorted(P[ans1[0]:ans1[1] + 1])
            #result += max(buf[:-1])
            result.append(max(buf[:-1]))
            #result.append(ans1)
        else:
            ncr(n1, r,N,P, ans1, result)
    return result
print(sum(ncr(list(range(N)),2,N,P)))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
p = list(map(int, input().split()))
sum = 0
for L in range(1,n):
  for R in range(L+1,n+1):
    max = 0
    second = 0
    for i in range(L-1,R):
      if p[i] > max:
        second = max
        max = p[i]
      elif p[i] > second:
        second = p[i]
    sum += second

print(sum)

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())

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

r1 = 0
for i1 in range(n1 - 1):
    for i2 in range(n1 - i1 - 1):
        n3 = n2[i1:i1 + i2 + 2]
        n3.sort(reverse=True)
        r1 += n3[1]

print(r1)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N = int(input())
    P = list(map(int, input().split()))
    ans = 0
    for i in range(N-1):
        fir = P[i]
        sec = 0
        for j in range(i+1, N):
            if fir < P[j]:
                sec = fir
                fir = P[j]
            elif sec < P[j]:
                sec = P[j]
            ans += sec
    print(ans)

Submission status: Time Limit Exceeded

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

ans=0

for i in range(n-1):
  li=p[i:i+2]
  a1=max(li)
  a2=min(li)
  for j in range(i+1,n):
    if a2<=p[j]<a1:
      a2=p[j]
    elif a1<p[j]:
      a2=a1
      a1=p[j]
    ans+=a2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    data = read()
    result = think(data)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(data):
    n = len(data)
    dp = [[0 for x in range(n)] for y in range(n)]

    # dp[left][right] is second maximum value about pair(L, R)

    for i in range(n - 1):
        dp[i][i + 1] = min(data[i], data[i + 1])
    for left in range(0, n - 1):
        for right in range(left + 2, n):
            if dp[left][right - 1] > data[right]:
                dp[left][right] = dp[left][right - 1]
            else:
                buf = data[:right + 1]
                buf = buf[left:]
                buf.sort(key=lambda x: -x)
                dp[left][right] = buf[1]

    total = 0
    for y in range(n):
        total += sum(dp[y])
    return total


def write(result):
    print(result)


if __name__ == '__main__':
    # import doctest
    # doctest.testmod()
    # import sys
    # sys.setrecursionlimit(10000)
    solve()

Submission status: Time Limit Exceeded

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

ans = 0
for L in range(n-1):
	for R in range(L+1, n):
		if L+1 == R:
			if p[L] > p[R]:
				big1 = p[L]
				big2 = p[R]
			else:
				big1 = p[R]
				big2 = p[L]
		else:
			if big1 < p[R]:
				big2 = big1
				big1 = p[R]
			elif big2 < p[R]:
				big2 = p[R]
		ans += big2

print(ans)

Submission status: Time Limit Exceeded

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

sum_so_far = 0
for L in range(N-1):
    largest = max(P[L], P[L+1])
    second = min(P[L], P[L+1])
    sum_so_far += second
    for R in range(L+2, N):
        if P[R] > second:
            second = P[R]
            if second > largest:
                largest, second = second, largest
        sum_so_far += second
print(sum_so_far)

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], reverse=True)[1]

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

    print(s)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys


def main():
    N = int(input())
    arr = np.array(input().split(), dtype='int64')

    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            #print(i,j)
            arr_sub = arr[i:j+1]
            #print(arr_sub)
            arr_sub = np.unique(arr_sub)
            #print(arr_sub)
            arr_sub = np.sort(arr_sub)
            #print(arr_sub)
            ans += arr_sub[-2]
    print(ans)







if __name__ =='__main__':
    main()