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()))
res = 0
for i in range(N):
    if P[i] == N:
        continue
    l1 = i - 1
    r1 =  i + 1
    while l1 >= 0 and P[l1] < P[i]:
        l1 -= 1
    while r1 < N and P[r1] < P[i]:
        r1 += 1
    l2 = l1 - 1
    r2 = r1 + 1
    while l2 >= 0 and P[l2] < P[i]:
        l2 -= 1
    while r2 < N and P[r2] < P[i]:
        r2 += 1
    if l1 == - 1:
        res += P[i]*(i + 1)*(r2 - r1)
    elif r1 == N:
        res += P[i]*(l1 - l2)*(N - i)
    else:
        res += P[i]*((l1 - l2)*(r1 - i) + (i - l1)*(r2 - r1))
print(res)

Submission status: Time Limit Exceeded

Solution code:

def main():
    N = int(input())
    P = [int(x) for x in input().split()]

    ans = 0
    # [key second,first:gain]のリストを更新していく
    calc_result = {}
    for R in range(1, N):
        first_val = P[R-1]
        second_val = 0
        key_name = "{0},{1}".format(second_val, first_val)
        calc_result[key_name] = 1
        calc_result_new = {}
        for c in calc_result:
            # 値の更新
            second_val, first_val = [int(x) for x in c.split(',')]
            if second_val < P[R] <= first_val:
                second_val = P[R]
            elif first_val < P[R]:
                second_val = first_val
                first_val = P[R]

            ans += second_val * calc_result[c]

            new_key = "{0},{1}".format(second_val, first_val)

            if new_key in calc_result_new:
                calc_result_new[new_key] += calc_result[c]
            else:
                calc_result_new[new_key] = calc_result[c]

        calc_result = calc_result_new

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    ans = 0
    # [gain, second, first]のリストを更新していく
    calc_result_list = []
    for R in range(1, N):
        gain = 1
        first_val = P[R-1]
        second_val = 0
        calc_result_list.append([gain, second_val, first_val])
        calc_result_list = sorted(calc_result_list, key=lambda x: (x[2], x[1]))
        new_calc_result = [calc_result_list[0]]
        for idx in range(0, len(calc_result_list)):
            # 値の更新
            if calc_result_list[idx][1] < P[R] <= calc_result_list[idx][2]:
                calc_result_list[idx][1] = P[R]
            elif calc_result_list[idx][2] < P[R]:
                calc_result_list[idx][1] = calc_result_list[idx][2]
                calc_result_list[idx][2] = P[R]

            ans += calc_result_list[idx][1] * calc_result_list[idx][0]

            if idx == 0:
                continue

            if new_calc_result[-1][2] == calc_result_list[idx][2] and new_calc_result[-1][1] == calc_result_list[idx][1]:
                new_calc_result[-1][0] += calc_result_list[idx][0]
            else:
                new_calc_result.append(calc_result_list[idx])
        calc_result_list = new_calc_result

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    N = int(input())
    P = [int(x) for x in input().split()]

    ans = 0
    # [gain, second, first]のリストを更新していく
    calc_result_list = []
    for R in range(1, N):
        gain = 1
        first_val = P[R-1]
        second_val = 0
        calc_result_list.append([gain, second_val, first_val])
        calc_result_list = sorted(calc_result_list, key=lambda x: (x[2], x[1]))
        new_calc_result = [calc_result_list[0]]
        for idx in range(0, len(calc_result_list)):
            # 値の更新
            if calc_result_list[idx][1] < P[R] <= calc_result_list[idx][2]:
                calc_result_list[idx][1] = P[R]
            elif calc_result_list[idx][2] < P[R]:
                calc_result_list[idx][1] = calc_result_list[idx][2]
                calc_result_list[idx][2] = P[R]

            ans += calc_result_list[idx][1] * calc_result_list[idx][0]

            if idx == 0:
                continue

            if new_calc_result[-1][2] == calc_result_list[idx][2] and new_calc_result[-1][1] == calc_result_list[idx][1]:
                new_calc_result[-1][0] += calc_result_list[idx][0]
            else:
                new_calc_result.append(calc_result_list[idx])
        calc_result_list = new_calc_result

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    N = int(input())
    P = [int(x) for x in input().split()]

    ans = 0
    for L in range(N-1):
        first_val = max(P[L], P[L+1])
        second_val = min(P[L], P[L+1])
        ans += second_val
        for R in range(L+2, N):
            if second_val < P[R] <= first_val:
                second_val = P[R]
            elif first_val < P[R]:
                second_val = first_val
                first_val = P[R]
            ans += second_val
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n):
    data[p[i]]=i+1
lst=[data[n]]
ans=0
if data[n-1]>data[n]:
    lst.append(data[n-1])
    a=lst[0]*(n-lst[1]+1)
    ans+=a*(n-1)
else:
    lst=[data[n-1]]+lst
    a=lst[0]*(n-lst[1]+1)
    ans+=a*(n-1)
lst.append(n+1)
lst=[0]+lst
for i in range(2,n):
    h=data[n-i]
    y=bisect(lst,h)
    L=len(lst)
    if y==1:
        a=h*(lst[2]-lst[1])
        ans+=a*(n-i)
        lst=[lst[0]]+[h]+lst[1:]
    elif y==L-1:
        a=(n-h+1)*(lst[-2]-lst[-3])
        ans+=a*(n-i)
        lst=lst[:(L-1)]+[h]+[lst[-1]]
    else:
        a=(lst[y+1]-lst[y])*(h-lst[y-1])+(lst[y]-h)*(lst[y-1]-lst[y-2])
        ans+=a*(n-i)
        lst=lst[:y]+[h]+lst[y:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n):
    data[p[i]]=i+1
lst=[data[n]]
ans=0
if data[n-1]>data[n]:
    lst.append(data[n-1])
    ans+=(lst[0]*(n-lst[1]+1))*(n-1)
else:
    lst=[data[n-1]]+lst
    ans+=(lst[0]*(n-lst[1]+1))*(n-1)
lst.append(n+1)
lst=[0]+lst
for i in range(2,n):
    h=data[n-i]
    y=bisect(lst,h)
    if y==1:
        ans+=(h*(lst[2]-lst[1]))*(n-i)
        lst=[lst[0]]+[h]+lst[1:]
    elif y==len(lst)-1:
        ans+=((n-h+1)*(lst[-2]-lst[-3]))*(n-i)
        lst=lst[:(len(lst)-1)]+[h]+[lst[-1]]
    else:
        ans+=((lst[y+1]-lst[y])*(h-lst[y-1])+(lst[y]-h)*(lst[y-1]-lst[y-2]))*(n-i)
        lst=lst[:y]+[h]+lst[y:]
print(ans)

Submission status: Time Limit Exceeded

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

for l in range(n - 1):
    for r in range(l + 1, n):
        sb = p[l:r + 1]
        sb.remove(max(sb))
        to += max(sb)
print(to)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
l=0
r=2
a=0
while l<n-1:
  p1=p[l:r]
  p1.remove(max(p1))
  a+=max(p1)
  r+=1
  if r==n+1:
    l+=1
    r=l+2
print(a)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    p = list(map(int, input().split()))
    inds = sorted([(i, p[i]) for i in range(N)], key=lambda x: -x[1])
    ans = 0
    s = [-1, -1, N, N]
    for ind, num in inds:
        l = bisect.bisect_left(s, ind)
        w, x, y, z = s[l-2], s[l-1], s[l], s[l+1]
        ans += num * ((x-w)*(y-ind) + (ind-x)*(z-y))
        s.insert(l, ind)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    p = list(map(int, input().split()))
    inds = sorted([(i, p[i]) for i in range(N)], key=lambda x: -x[1])
    ans = 0
    s = [-1, -1, N, N]
    for ind, num in inds:
        l = bisect.bisect_left(s, ind)
        w, x, y, z = s[l-2], s[l-1], s[l], s[l+1]
        ans += num * ((x-w)*(y-ind) + (ind-x)*(z-y))
        s = s[:l] + [ind] + s[l:]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    p = list(map(int, input().split()))
    inds = sorted(range(N), key=lambda i: p[i], reverse=True)
    ans = 0
    s = [-1, -1, N, N]
    pre_l = 0
    pre_ind = -1
    for ind in inds:
        if pre_ind < ind:
            l = bisect.bisect_left(s, ind, pre_l, len(s))
        else:
            l = bisect.bisect_left(s, ind, 0, pre_l)
        w, x, y, z = s[l-2], s[l-1], s[l], s[l+1]
        ans += p[ind] * ((x-w)*(y-ind) + (ind-x)*(z-y))
        s.insert(l, ind)
        pre_l = l
        pre_ind = ind
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    p = list(map(int, input().split()))
    inds = sorted(range(N), key=lambda i: p[i], reverse=True)
    ans = 0
    s = [-1, -1, N, N]
    for ind in inds:
        t = bisect.bisect_left(s, ind)
        w, x, y, z = s[t-2], s[t-1], s[t], s[t+1]
        tmp = p[ind] * ((x-w)*(y-ind) + (ind-x)*(z-y))
        # print(p[ind], w, x, ind, y, z)
        # print(s)
        ans += tmp
        s.insert(t, ind)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for l in range(n - 1):
    for r in range(l + 1, n):
        sb = p[l:r + 1]
        sb.sort()
        if len(sb) > 1:
            s = sb[-2]
        else:
            s = sb[0]
        to += s
print(to)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(2, N+1):
    for j in range(N-i+1):
        tmp = sorted(set(P[j:j+i]), reverse=True)[1]
        ans += tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n = int(input())
p = []

for i, x in enumerate(map(int, input().split())):
    p.append([x, i])

p.sort(reverse=True)

s = [-1, -1, p[0][1], n, n]

#print(p)

ans = 0
i = 2
for a, x in p[1:]:
    t = bisect_left(s, x)
    ans += a * ((x - s[t-1]) * (s[t+1] - s[t]) + (s[t] - x) * (s[t-1] - s[t-2]))
    #print(t, s)
    s.insert(t, x)
    i += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc140/tasks/abc140_e
n = int(input())
p = list(map(int, input().split()))
sum = 0
for i in range(len(p)): 
    for j in range(i+1, len(p)):
        sum += sorted(p[i:j+1])[-2]

print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int,input().split()))
ans = 0
for x in range(N-1):
  l = list()
  l.append(P[x])
  for y in range(N-1-x):
    l.append(P[x+1+y])
    ans += sorted(l)[-2]
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for l in range(N-1):
    for r in range(l+1,N):
        ans += sorted(P[l:r+1])[-2]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    P = [None] + list(map(int, input().split()))

    p_to_index = [None] * (N + 1)
    for index, x in enumerate(P[1:], 1):
        p_to_index[x] = index

    #大きい数から挿入
    #左隣にあるインデックスを取得できるようにする
    #[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):
        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)
    ans = 0
    for x in range(N, 0, -1):
        c = p_to_index[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
        if b != 0:
            ans += x * (b - a) * (d - c)
        if d != 0:
            ans += x * (e - d) * (c - b)

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [None] + list(map(int, input().split()))

p_to_index = [None] * (N + 1)
for index, x in enumerate(P[1:], 1):
    p_to_index[x] = index

#大きい数から挿入
#左隣にあるインデックスを取得できるようにする
#[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):
    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)
ans = 0
for x in range(N, 0, -1):
    c = p_to_index[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
    tmp = 0
    if b != 0:
        tmp += (b - a) * (d - c)
    if d != 0:
        tmp += (e - d) * (c - b)
    ans += tmp * x

print (ans)

Submission status: Time Limit Exceeded

Solution code:
# E - E - Second Sum
import sys
import heapq

input = sys.stdin.readline

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

# print(P)
i = 2
for i in range(2, N + 1, 1):
#    print(i)
    for j in range(0, N - i + 1, 1):
#        print("target slice is {}".format(P[j: j + i]))
        tmp = P[j: j + i]
        heapq.heapify(tmp)
        heapq.heappop(tmp)
        sum += heapq.heappop(tmp)

print(-sum)

Submission status: Time Limit Exceeded

Solution code:
# E - E - Second Sum
import sys
import heapq

input = sys.stdin.readline

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

# print(P)
i = 2
while i <= N:
#     print(i)
    q = []
    j = 0
    while j + i <= N:
#         print("target slice is {}".format(P[j: j + i]))
        tmp = P[j: j + i]
        heapq.heapify(tmp)
        heapq.heappop(tmp)
        sum += heapq.heappop(tmp)

        j += 1

    i += 1

print(-sum)

Submission status: Time Limit Exceeded

Solution code:
class SegTree:

    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n = int(input())
xs = list(map(int, input().split()))
x2i = {}
for i, x in enumerate(xs):
    x2i[x] = i
ss1 = SegTree([n] * n, n, n, min)
ss2 = SegTree([-1] * n, n, -1, max)

r = 0
for x in range(n):
    x = n - x
    rmi2 = ss1.query(x2i[x]+1, n)
    if rmi2 != n:
        ss1.update(rmi2, n)
    rmi = ss1.query(x2i[x]+1, n)
    if rmi2 != n:
        ss1.update(rmi2, rmi2)

    lmi = ss2.query(0, x2i[x])
    if lmi != -1:
        ss2.update(lmi, -1)
    lmi2 = ss2.query(0, x2i[x])
    if lmi != -1:
        ss2.update(lmi, lmi)
    a,b,c,d =(x2i[x] - lmi), (lmi - lmi2), (rmi - rmi2), (rmi2 - x2i[x])
    r += (a*c + b*d) * x
#    print(x, r)
#    print(rmi, rmi2, lmi, lmi2)
    ss1.update(x2i[x], x2i[x])
    ss2.update(x2i[x], x2i[x])
print(r)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xs = list(map(int, input().split()))
x2i = {}
for i, x in enumerate(xs):
    x2i[x] = i+1
ll = [0] * (n+2)
rr = [n+1] * (n+2)

def find_l(l, r, default):
    m, m2 = 0, 0
    mi=mi2=default
    for i in range(r-l):
        i = i + l
        if ll[i] > m:
            mi, m = i, ll[i]
    for i in range(r-l):
        i = i + l
        if i == mi:
            continue
        if ll[i] > m2:
            mi2, m2 = i, ll[i]
    return max(mi, mi2), min(mi, mi2)

def find_r(l, r, default):
    m, m2 = n+1, n+1
    mi=mi2=default
    for i in range(r-l):
        i = i + l
        if rr[i] < m:
            mi, m = i, rr[i]
    for i in range(r-l):
        i = i + l
        if i == mi:
            continue
        if rr[i] < m2:
            mi2, m2 = i, rr[i]
    return max(mi, mi2), min(mi, mi2)

def segfunc(x, y):
    return min(x, y)

def init(init_val):
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(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] = segfunc(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 = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele = n+1
n = n + 2
num = 2**(n-1).bit_length()
n = n - 2
seg=[ide_ele]*2*num

init(rr)

r = 0
for x in range(n):
    x = n - x
    lmi, lmi2 = find_l(0, x2i[x], 0)
    rmi2 = query(x2i[x]+1, n+1)
    update(rmi2, n+1)
    rmi = query(x2i[x]+1, n+1)
    update(rmi2, rmi2)
    #rmi, rmi2 = max
    a,b,c,d =(x2i[x] - lmi), (lmi - lmi2), (rmi - rmi2), (rmi2 - x2i[x])
    r += (a*c + b*d) * x
#    print(x, r)
#    print(rmi, rmi2, lmi, lmi2)
    ll[x2i[x]] = x2i[x]
    update(x2i[x], x2i[x])
print(r)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xs = list(map(int, input().split()))
x2i = {}
for i, x in enumerate(xs):
    x2i[x] = i+1
ll = [0] * (n+2)
rr = [n+1] * (n+2)

def find_l(l, r, default):
    m, m2 = 0, 0
    mi=mi2=default
    for i in range(r-l):
        i = i + l
        if ll[i] > m:
            mi, m = i, ll[i]
    for i in range(r-l):
        i = i + l
        if i == mi:
            continue
        if ll[i] > m2:
            mi2, m2 = i, ll[i]
    return max(mi, mi2), min(mi, mi2)

def find_r(l, r, default):
    m, m2 = n+1, n+1
    mi=mi2=default
    for i in range(r-l):
        i = i + l
        if rr[i] < m:
            mi, m = i, rr[i]
    for i in range(r-l):
        i = i + l
        if i == mi:
            continue
        if rr[i] < m2:
            mi2, m2 = i, rr[i]
    return max(mi, mi2), min(mi, mi2)

r = 0
for x in range(n):
    x = n - x
    lmi, lmi2 = find_l(0, x2i[x], 0)
    rmi, rmi2 = find_r(x2i[x]+1, n+1, n+1)
    a,b,c,d =(x2i[x] - lmi), (lmi - lmi2), (rmi - rmi2), (rmi2 - x2i[x])
    r += (a*c + b*d) * x
#    print(x, r)
#    print(rmi, rmi2, lmi, lmi2)
    ll[x2i[x]] = x2i[x]
    rr[x2i[x]] = x2i[x]
print(r)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    N = int(input())
    P = [int(i) for i in input().split()]
    count = 0
    for i in range(N-1):
        heap = []
        heapq.heappush(heap, P[i] * -1)
        for j in range(i+1,N):
            heapq.heappush(heap, P[j] * -1)
            A = heapq.heappop(heap)
            B = heapq.heappop(heap)
            count += B * -1
            heapq.heappush(heap,A)
            heapq.heappush(heap,B)
        
    print(count)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
Pi=list(map(int,input().split()))
sum=0

for L in range(N-1):
    for R in range(L+1,N):
        lst=Pi[L:R+1]
        a=max(lst)
        lst.remove(a)
        X=max(lst)
        sum+=X
print(sum)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12_rec(i, j, segi):
        if j - i <= 0:
            return (0, 0)
        seg = segt[segi]
        if j - i == 1:
            return seg[i]
        arr = []
        if i % 2 == 1:
            a, b = seg[i]
            arr.append(a)
            arr.append(b)
            i += 1
        if j % 2 == 1:
            a, b = seg[j - 1]
            arr.append(a)
            arr.append(b)
            j -= 1
        a, b = get12_rec(i // 2, j // 2, segi + 1)
        arr.append(a)
        arr.append(b)
        arr.sort()
        return arr[-1], arr[-2]

    def get12(i, j):
        return get12_rec(i, j, 0)

    cache = [dict() for _ in range(N)]

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if j in cache[i]:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or d in cache[c]):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[c][d]
                                    for c, d in want]
                cache[i][j] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[c][d]
                            for c, d in want]
        cache[i][j] = left + right - mid + sc

    return cache[0][N]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12_rec(i, j, segi):
        if j - i <= 0:
            return (0, 0)
        seg = segt[segi]
        if j - i == 1:
            return seg[i]
        arr = []
        if i % 2 == 1:
            a, b = seg[i]
            arr.append(a)
            arr.append(b)
            i += 1
        if j % 2 == 1:
            a, b = seg[j - 1]
            arr.append(a)
            arr.append(b)
            j -= 1
        a, b = get12_rec(i // 2, j // 2, segi + 1)
        arr.append(a)
        arr.append(b)
        arr.sort()
        return arr[-1], arr[-2]

    def get12(i, j):
        return get12_rec(i, j, 0)

    cache = {}

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if (i, j) in cache:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or (c, d) in cache):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[(c, d)]
                                    for c, d in want]
                cache[(i, j)] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[(c, d)]
                            for c, d in want]
        cache[(i, j)] = left + right - mid + sc

    return cache[(0, N)]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop


def calc(idx, left, right):
    while -left[0] > idx:
        x = -heappop(left)
        heappush(right, x)
    while right[0] < idx:
        x = heappop(right)
        heappush(left, -x)
    ret = 0
    l = -heappop(left)
    r = heappop(right)
    ret += (right[0] - r) * (idx - l) + \
           (l - (-left[0])) * (r - idx)
    heappush(left, -l)
    heappush(right, r)
    heappush(right, idx)
    return ret


def main():
    N = int(input())
    P = list(map(int, input().split()))
    idx = [0] * N
    for i in range(N):
        idx[P[i]-1] = i
    left = [1, 1]
    right = [N, N]
    ans = 0
    for i in range(N)[::-1]:
        x = calc(idx[i], left, right)
        ans += (i+1) * x
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0
bi = []
for i in range(n, 0, -1):
    a = -1
    b = -1
    c = n
    d = n
    point = bisect.bisect(bi, pp[i])
    if point != 0:
        b = bi[point-1]
        if point != 1:
            a = bi[point-2]

    if point != len(bi):
        c = bi[point]
        if point != len(bi)-1:
            d = bi[point+1]

    bisect.insort(bi, pp[i])




    ans += (b-a)*(c-pp[i])*i + (d-c)*(pp[i]-b)*i

print(ans)

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

Submission status: Time Limit Exceeded

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



total = 0

for L in range(N-1):
	for R in range(L + 1, N):
		B = P[L:R + 1]
		maxValue = max(B)
		B.pop(B.index(maxValue))
		
		sec_max = max(B)
		x = sec_max
		total += x
print(total)

Submission status: Time Limit Exceeded

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



total = 0 
for L in range(N-1):
	for R in range(L + 1, N):
		B = set(P[L:R + 1])
		maxValue = max(B)
		B.remove(maxValue)
		sec_max = max(B)
		x = sec_max
		total += x
print(total)

Submission status: Time Limit Exceeded

Solution code:
def secmax(temp):
	if(len(temp)>=2):
		temp.remove(max(temp))
		return(max(temp))
	else:
		return(temp[0])
n = int(input())
a = [int(i) for i in input().split(" ")]
s = 0
for i in range(n-1):
	for j in range(i+1,n):
		s += secmax(a[i:j+1])
		# print(i,j," ",s)
print(s)

Submission status: Time Limit Exceeded

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

sum = 0
for L in range(len(P)-1):
    for R in range(L+1,len(P)):
        part = P[L:R+1]
        part.remove(max(part))
        sum += max(part)

print(sum)

Submission status: Time Limit Exceeded

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

sum = 0
for L in range(len(P)-1):
    for R in range(L+1,len(P)):
        sortlist = sorted(P[L:R+1])
        sum += sortlist[len(sortlist)-2]

print(sum)