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:
class SegmentTree:
    """
    値をlistで持つSegmentTree
    update(i, x): i(0-indexed)をxで更新
    get(a,b): [a, b)を取得
    """

    def __init__(self, n, ini, merge):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [ini.copy() for _ in range(n2 << 1)]
        self.ini = ini
        self.merge = merge

    def update(self, i, x):
        i += self.n2
        self.tree[i] = self.merge(x, self.tree[i])
        while i > 1:
            self.tree[i >> 1] = x = self.merge(x, self.tree[i ^ 1])
            i >>= 1

    def get(self, a, b):
        return self._get(a, b, 1, 0, self.n2)

    def _get(self, a, b, k, l, r):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での値
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return self.ini
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            return self.tree[k]
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        return self.merge(self._get(a, b, k << 1, l, m), self._get(a, b, (k << 1) + 1, m, r))


def solve(n, ppp):
    def merge_min(x, y):
        if x[0] <= y[0]:
            if x[1] <= y[0]:
                return x.copy()
            return [x[0], y[0]]
        if x[0] <= y[1]:
            return [y[0], x[0]]
        return y.copy()

    def merge_max(x, y):
        if x[0] >= y[0]:
            if x[1] >= y[0]:
                return x.copy()
            return [x[0], y[0]]
        if x[0] >= y[1]:
            return [y[0], x[0]]
        return y.copy()

    stl = SegmentTree(n, [-1, -1], merge_max)
    left1 = [-1] * n
    left2 = [-1] * n
    for i, p in enumerate(ppp):
        res = stl.get(p, n)
        left1[i] = res[0]
        left2[i] = res[1]
        stl.update(p - 1, [i, -1])

    str = SegmentTree(n, [n, n], merge_min)
    right1 = [n] * n
    right2 = [n] * n
    for i, p in enumerate(ppp[::-1]):
        i = n - i - 1
        res = str.get(p, n)
        right1[i] = res[0]
        right2[i] = res[1]
        str.update(p - 1, [i, n])
    # print(left1)
    # print(left2)
    # print(right1)
    # print(right2)

    ans = 0
    for i, l1, l2, r1, r2 in zip(range(n), left1, left2, right1, right2):
        ans += ppp[i] * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

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):
        q = p[i:j+1]
        q.remove(max(q))
        count += max(q)
print(count)

Submission status: Time Limit Exceeded

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N = int(input())
P = list(map(int, input().split()))
s = 0

for i in range(N):
    a1 = None
    a2 = None
    b1 = None
    b2 = None
    key = P[i]

    for p in reversed(P[0:i]):
        if p > key:
            if a1 is None:
                a1 = P.index(p)
            else:
                a2 = P.index(p)
                break
    for p in P[i+1:N]:
        if p > key:
            if b1 is None:
                b1 = P.index(p)
            else:
                b2 = P.index(p)
                break

    if a1 is not None:
        _a2 = -1 if a2 is None else a2
        _b1 = N if b1 is None else b1
        s += ((a1 - _a2) * (_b1 - i))*key

    if b1 is not None:
        _b2 = N if b2 is None else b2
        _a1 = -1 if a1 is None else a1
        s += ((_b2 - b1) * (i - _a1))*key

print(str(s))

Submission status: Time Limit Exceeded

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

for i in range(N):
    a1 = None
    a2 = None
    b1 = None
    b2 = None
    key = P[i]

    for p in reversed(P[0:i]):
        if p > key:
            a1 = P.index(p)
            break
    if a1 is not None:
        for p in reversed(P[0:a1]):
            if p > key:
                a2 = P.index(p)
                break
    for p in P[i+1:N]:
        if p > key:
            b1 = P.index(p)
            break
    if b1 is not None:
        for p in P[b1+1:N]:
            if p > key:
                b2 = P.index(p)
                break

    if a1 is not None:
        _a2 = -1 if a2 is None else a2
        _b1 = N if b1 is None else b1
        s += ((a1 - _a2) * (_b1 - i))*key

    if b1 is not None:
        _b2 = N if b2 is None else b2
        _a1 = -1 if a1 is None else a1
        s += ((_b2 - b1) * (i - _a1))*key

print(str(s))

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):
		L1ind, L2ind = -1, -1
		R1ind, R2ind = N, N
		indt = L-1
		while L2ind==-1 and indt>=0:
			if P[indt]>=P[L]:
				if L1ind==-1:
					L1ind = indt
				elif L2ind==-1:
					L2ind = indt
			indt -= 1

		indt = L+1
		while R2ind==N and indt<=N-1:
			if P[indt]>=P[L]:
				if R1ind==N:
					R1ind = indt
				elif R2ind==N:
					R2ind = indt		
			indt += 1

		x += ((L1ind-L2ind)*(R1ind-L) + (L-L1ind)*(R2ind-R1ind))*P[L]

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(N):
    a1 = None
    a2 = None
    b1 = None
    b2 = None
    key = P[i]
    tmp = i

    while tmp > 0:
        tmp -= 1
        if P[tmp] > key:
            a1 = tmp
            break
    while tmp > 0:
        tmp -= 1
        if P[tmp] > key:
            a2 = tmp
            break

    tmp = i
    while tmp < N - 1:
        tmp += 1
        if P[tmp] > key:
            b1 = tmp
            break
    while tmp < N - 1:
        tmp += 1
        if P[tmp] > key:
            b2 = tmp
            break

    if a1 is not None:
        _a2 = -1 if a2 is None else a2
        _b1 = N if b1 is None else b1
        s += ((a1 - _a2) * (_b1 - i))*key

    if b1 is not None:
        _b2 = N if b2 is None else b2
        _a1 = -1 if a1 is None else a1
        s += ((_b2 - b1) * (i - _a1))*key

print(str(s))

Submission status: Time Limit Exceeded

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N = int(input())
P = list(map(int, input().split()))
s = 0

for i in range(N):
    a1 = None
    a2 = None
    b1 = None
    b2 = None
    key = P[i]
    tmp = i

    while tmp > 0:
        tmp -= 1
        if P[tmp] > key:
            a1 = tmp
            break
    while tmp > 0:
        tmp -= 1
        if P[tmp] > key:
            a2 = tmp
            break

    tmp = i
    while tmp < N - 1:
        tmp += 1
        if P[tmp] > key:
            b1 = tmp
            break
    while tmp < N - 1:
        tmp += 1
        if P[tmp] > key:
            b2 = tmp
            break

    if a1 is not None:
        _a2 = -1 if a2 is None else a2
        _b1 = N if b1 is None else b1
        s += ((a1 - _a2) * (_b1 - i))*key

    if b1 is not None:
        _b2 = N if b2 is None else b2
        _a1 = -1 if a1 is None else a1
        s += ((_b2 - b1) * (i - _a1))*key

print(str(s))

Submission status: Time Limit Exceeded

Solution code:
import bisect
 
n = int(input())
P = list(map(int, input().split(" ")))
index = sorted(range(n), key=lambda k: P[k], reverse=True)
bi = [-1,-1,n,n]
bisect.insort(bi,index[0])
C = 0
lc = 0
rc = 0
C1 = 0
for i in index[1:]:
  #bisect.insort(bi,i)
  l = bisect.bisect_left(bi,i)
  lc = bi[l-1] - bi[l-2]
  rc = bi[l] - i
  C1 = lc*rc
  lc = i - bi[l-1]
  rc = bi[l+1] - bi[l]
  C1 += lc*rc
  C += (P[i]*C1)
  bisect.insort(bi,i)
  
print(C)

Submission status: Time Limit Exceeded

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

for i in range(N):
    a1 = None
    a2 = None
    b1 = None
    b2 = None

    tmp = i
    while tmp > 0:
        tmp -= 1
        if P[tmp] > P[i]:
            a1 = tmp
            break
    while tmp > 0:
        tmp -= 1
        if P[tmp] > P[i]:
            a2 = tmp
            break

    tmp = i
    while tmp < N-1:
        tmp += 1
        if P[tmp] > P[i]:
            b1 = tmp
            break
    while tmp < N - 1:
        tmp += 1
        if P[tmp] > P[i]:
            b2 = tmp
            break
    if a1 is not None:
        _a2 = -1 if a2 is None else a2
        _b1 = N if b1 is None else b1
        s += ((a1 - _a2) * (_b1 - i))*P[i]

    if b1 is not None:
        _b2 = N if b2 is None else b2
        _a1 = -1 if a1 is None else a1
        s += ((_b2 - b1) * (i - _a1))*P[i]
print(str(s))

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():

    N = int(input())
    P = list(map(int, input().split()))
    P = [[P[i], i+1] for i in range(N)]
    P.sort(key = lambda x: x[0], reverse = True)

    S, T = [], []
    heapq.heappush(S, 0)
    heapq.heappush(S, 0)
    heapq.heappush(T, N+1)
    heapq.heappush(T, N+1)
    ans = 0
    for i in range(N):
        p, k = P[i]
        while S and -S[0] > k:
            j = - heapq.heappop(S)
            heapq.heappush(T, j)
        while T and T[0] < k:
            j = -heapq.heappop(T)
            heapq.heappush(S, j)
        a = heapq.heappop(S)
        b = heapq.heappop(S)
        c = heapq.heappop(T)
        d = heapq.heappop(T)
        ct = (-a+b)*(c-k) + (d-c)*(k+a)
        heapq.heappush(S, a)
        heapq.heappush(S, b)
        heapq.heappush(T, c)
        heapq.heappush(T, d)
        # print(ct)
        ans += ct * p
        # heapq.heapify(S)
        # heapq.heapify(T)
        # print(S, T, p, i, ans, ct)
        heapq.heappush(T, k)
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import bisect
 
n = int(input())
P = list(map(int, input().split(" ")))
index = sorted(range(n), key=lambda k: P[k], reverse=True)
bi = []
bisect.insort(bi,index[0])
C = 0
lc = 0
rc = 0
C1 = 0
for i in index[1:]:
  #bisect.insort(bi,i)
  l = bisect.bisect_left(bi,i)
  if l == 0:
    lc = i + 1
    if len(bi) == 1:
      rc = n - bi[0]
    else:
      rc = bi[l+1] - bi[l]
    C1 = lc*rc
  elif l == len(bi):
    if len(bi) == 1:
      lc = bi[0] + 1
    else:
      lc = bi[l-1] - bi[l-2]
    rc = n - i
    C1 = lc*rc
  else: 
    if len(bi) == 2:
      lc = bi[0] + 1
      rc = bi[1] - i
      C1 = lc*rc
      lc = i - bi[0]
      rc = n - bi[1]
      C1 += lc*rc
    elif l == 1:
      lc = bi[0] + 1
      rc = bi[1] - i
      C1 = lc*rc
      lc = i - bi[0]
      rc = bi[2] - bi[1]
      C1 += lc*rc
    elif l == len(bi) - 1:
      lc = bi[l-1] - bi[l-2]
      rc = bi[l] - i
      C1 = lc*rc
      lc = i - bi[l-1]
      rc = n - bi[l]
      C1 += lc*rc
    else:
      lc = bi[l-1] - bi[l-2]
      rc = bi[l] - i
      C1 = lc*rc
      lc = i - bi[l-1]
      rc = bi[l+1] - bi[l]
      C1 += lc*rc
  C += (P[i]*C1)
  bisect.insort(bi,i)
  
print(C)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [int(i) for i in input().split()]
sum = 0
for i in range(n-1):
    for j in range(i+1,n):
        data = p[i:j+1]
        data.remove(max(data))
        sum += max(data)

print(sum)

Submission status: Time Limit Exceeded

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

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

ans = 0
memo = [I[N-1]]

for p in range(N-1, 0, -1):
    i = I[p-1]
    b = bisect(memo, i)
    l1 = memo[b-1] if b > 0 else -1
    l2 = memo[b-2] if b > 1 else -1
    r1 = memo[b+0] if b < N-p else N
    r2 = memo[b+1] if b < N-p-1 else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))
    insort(memo, i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
#print(p)
ans=0
for i in range(n):
  z=n
  w=n
  for j in range(i+1,n):
    if p[i]<p[j]:
      z=j
      for k in range(j+1,n):
         if p[i]<p[k]:
            w=k
            break
      break
  x=-1
  y=-1
  for j in reversed(range(i)):
    if p[j]>p[i]:
      y=j
      for k in reversed(range(j)):
         if p[k]>p[i]:
            x=k
            break
      break
  #print(x,y,i,z,w)
  num=(y-x)*(z-i)+(w-z)*(i-y)
  #print(num)
  ans+=num*p[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    def X_lr(L, R):
        sorted_P = sorted(P[L-1:R], reverse=True)
#        print("### L=", L, " R=", R, " ", sorted_P)
        return sorted_P[1]

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

    total = 0
    for L in range(1, N-1+1):
        for R in range(L+1,N+1):
            total += X_lr(L,R)
    print(total)

main()

Submission status: Time Limit Exceeded

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

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

ans = 0
memo = [I[N-1]]

for p in range(N-1, 0, -1):
    i = I[p-1]
    l1, l2 = 0, 0
    r1, r2 = N-1, N-1
    for j in range(i-1, -1, -1):
        if j in memo:
            l1 = j
            break
    else:
        l1 = -1
    for j in range(l1-1, -1, -1):
        if j in memo:
            l2 = j
            break
    else:
        l2 = -1
    for j in range(i+1, N):
        if j in memo:
            r1 = j
            break
    else:
        r1 = N
    for j in range(r1+1, N):
        if j in memo:
            r2 = j
            break
    else:
        r2 = N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))
    memo.append(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=[0]+list(map(int, input().split()))
C=[0 for _ in range(N+1)]
index=[0 for _ in range(N+1)]
for i in range(1, N+1):
  index[P[i]]=i
for n in range(1, N+1):
  l, r=[0, 0], [N+1, N+1]
  for i in range(n+1, N+1):
    if index[i]<index[n]:
      if l[1]<index[i]:
        l=[l[1], index[i]]
      elif l[0]<index[i]:
        l=[index[i], l[1]]
    else:
      if index[i]<r[0]:
        r=[index[i], r[0]]
      elif index[i]<r[1]:
        r=[r[0], index[i]]
  C[n]=(l[1]-l[0])*(r[0]-index[n])+(index[n]-l[1])*(r[1]-r[0])
res=0
for i in range(N+1):
  res+=i*C[i]
print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
P = list(map(int, input().split(" ")))
sp = sorted(P, reverse=True)
bi = []
bisect.insort(bi,P.index(sp[0]))
C = 0
lc = 0
rc = 0
C1 = 0
for j in sp[1:]:
  i = P.index(j)
  #bisect.insort(bi,i)
  l = bisect.bisect_left(bi,i)
  if l == 0:
    lc = i + 1
    if len(bi) == 1:
      rc = n - bi[0]
    else:
      rc = bi[l+1] - bi[l]
    C1 = lc*rc
  elif l == len(bi):
    if len(bi) == 1:
      lc = bi[0] + 1
    else:
      lc = bi[l-1] - bi[l-2]
    rc = n - i
    C1 = lc*rc
  else: 
    if len(bi) == 2:
      lc = bi[0] + 1
      rc = bi[1] - i
      C1 = lc*rc
      lc = i - bi[0]
      rc = n - bi[1]
      C1 += lc*rc
    elif l == 1:
      lc = bi[0] + 1
      rc = bi[1] - i
      C1 = lc*rc
      lc = i - bi[0]
      rc = bi[2] - bi[1]
      C1 += lc*rc
    elif l == len(bi) - 1:
      lc = bi[l-1] - bi[l-2]
      rc = bi[l] - i
      C1 = lc*rc
      lc = i - bi[l-1]
      rc = n - bi[l]
      C1 += lc*rc
    else:
      lc = bi[l-1] - bi[l-2]
      rc = bi[l] - i
      C1 = lc*rc
      lc = i - bi[l-1]
      rc = bi[l+1] - bi[l]
      C1 += lc*rc
  C += (P[i]*C1)
  bisect.insort(bi,i)
  
print(C)

Submission status: Time Limit Exceeded

Solution code:
n = int(input(''))
p = [int(x) for x in str(input('')).split(' ')]
total = 0

for j in range (0, len(p)):
    prev = [p[j], -1]
    for i in range (j+1, len(p)):
        cur = prev
        cur.append(p[i])
        cur.remove(min(cur))
        total += min(cur)
        prev = cur
print(total)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(N, P):
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)
    done = [0, N+1]
    ans = 0
    for p, i in P2:
        i += 1
        j = bisect.bisect(done, i)
        bisect.insort(done, i)
        c = 0
        if j >= 2:
            l = done[j-1] - done[j-2]
            r = done[j+1] - done[j]
            c += l * r
        if j <= len(done) - 3:
            l = done[j] - done[j-1]
            r = done[j+2] - done[j+1]
            c += l*r
        ans += c*p
        
    return ans


@mt
def slv2(N, P):
    ans = 0
    c = Counter()
    for i, j in combinations(range(N), 2):
        a = sorted(P[i:j+1], reverse=True)[1]
        ans += a
        c[a] += 1
    print(c)
    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))
    # print(slv2(N, P))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
n = int(input())
P = np.array(list(map(int, input().split(" "))))
#SP = np.sort(P)[::-1]
index = np.argsort(P)[::-1]
bi = []
bisect.insort(bi,index[0])
C = 0
lc = 0
rc = 0
C1 = 0
for i in index[1:]:
  #bisect.insort(bi,i)
  l = bisect.bisect_left(bi,i)
  if l == 0:
    lc = i + 1
    if len(bi) == 1:
      rc = n - bi[0]
    else:
      rc = bi[l+1] - bi[l]
    C1 = lc*rc
  elif l == len(bi):
    if len(bi) == 1:
      lc = bi[0] + 1
    else:
      lc = bi[l-1] - bi[l-2]
    rc = n - i
    C1 = lc*rc
  else: 
    if len(bi) == 2:
      lc = bi[0] + 1
      rc = bi[1] - i
      C1 = lc*rc
      lc = i - bi[0]
      rc = n - bi[1]
      C1 += lc*rc
    elif l == 1:
      lc = bi[0] + 1
      rc = bi[1] - i
      C1 = lc*rc
      lc = i - bi[0]
      rc = bi[2] - bi[1]
      C1 += lc*rc
    elif l == len(bi) - 1:
      lc = bi[l-1] - bi[l-2]
      rc = bi[l] - i
      C1 = lc*rc
      lc = i - bi[l-1]
      rc = n - bi[l]
      C1 += lc*rc
    else:
      lc = bi[l-1] - bi[l-2]
      rc = bi[l] - i
      C1 = lc*rc
      lc = i - bi[l-1]
      rc = bi[l+1] - bi[l]
      C1 += lc*rc
  C += (P[i]*C1)
  bisect.insort(bi,i)
  
print(C)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
P=[int(i) for i in input().split()]
n_max=10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
def bitlb(BIT,s):
  if s<=0:
    return 0
  else:
    ret=0
    k=2**nn
    while k>0:
      if k+ret<=2**nn and BIT[k+ret]<s:
        s-=BIT[k+ret]
        ret+=k
      k//=2
    return ret+1
D=dict()
for i in range(n):
  D[P[i]]=i+1
PP=sorted(P,reverse=True)
bitadd(BIT,D[PP[0]],1)
ans=0
for i in range(1,n):
  cur=D[PP[i]]
  bitadd(BIT,cur,1)
  tot=bitsum(BIT,cur)
  l2,l1,r1,r2=bitlb(BIT,tot-2),bitlb(BIT,tot-1),min(n+1,bitlb(BIT,tot+1)),min(n+1,bitlb(BIT,tot+2))
  add=PP[i]*((-l1+cur)*(r2-r1)+(l1-l2)*(r1-cur))
  ans+=add
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getSize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
A = [0] + list(map(int, input().split())) + [N+1]
B = [None] * (N+2)
for i, x in enumerate(A):
    B[x] = i
A[0] = N+1
uf = UnionFind(N+1)
ans = 0
for x in range(1, N):
    i = B[x]
    if A[i-1] < A[i]:
        uf.unite(i-1, i)
    if A[i] > A[i+1]:
        uf.unite(i, i+1)
    if x < A[i-1]:
        k2 = i-1
    else:
        l, r = 0, i-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, i-1):
                r = m
            else:
                l = m
        k2 = l
    if k2 == 0 or A[max(0, k2-1)] > x:
        k1 = max(0, k2-1)
    else:
        l, r = 0, k2-1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(m, k2-1):
                r = m
            else:
                l = m
        k1 = l
    if x < A[i+1]:
        k3 = i+1
    else:
        l, r = i+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(i+1, m):
                l = m
            else:
                r = m
        k3 = r
    if k3 == N+1 or x < A[min(N+1, k3+1)]:
        k4 = min(N+1, k3+1)
    else:
        l, r = k3+1, N+1
        while l+1 < r:
            m = (l+r)//2
            if uf.same(k3+1, m):
                l = m
            else:
                r = m
        k4 = r
    ans += x * ((k2-k1)*(k3-i) + (k4-k3)*(i-k2))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# def add(x,y):
# 	return x+y

def main():

	input = sys.stdin.readline

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

	x = 0
	first = 0
	second = 0
	second_list = []
	scnd_acml = []
	for L in range(N):
		if P[L]>first:
			second = first
			first = P[L]
		elif P[L]>second:
			second = P[L]

		if L!=0:
			x = x+second
			second_list.append(second)
			scnd_acml.append(0)
			scnd_acml = list(map(lambda x:x+second, scnd_acml))

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

			if second==second_list[ind-1]:
				x = x+scnd_acml[ind-1]
				break
			else:
				x = x+second
		

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
s = 0
for i in range(n - 1):
    l = n
    while i + 1 != l:
        no1 = max(p[i: l])
        no2 = sorted(p[i: l])[-2]
        a = p.index(no1)
        b = p.index(no2)
        if p[i: l] == sorted(p[i: l]):
            s += sum(p[i: l - 1])
            break
        if a < b:
            s += (l - b) * no2
            l = b
        else:
            s += (l - a) * no2
            l = a
print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

P = []
P = input().split()
P = [int(n) for n in P]

tot = 0

for i in range(N-1) :
  for j in range(N-(i+1)) :
    XLR = []
    for k in range(j+2) :
      XLR.append(P[i+k])    
    XLR.sort(reverse=True)
#    print(XLR)
    tot = tot + XLR[1]

#print(N)
#print(P)

print(tot)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
n = int(input()) # Skip first line
p = list(map(int,input().split()))

k=[]
point=0
for i1 in range(n-1):
    i2 = i1 + 1
    if p[i1] < p [i2]: 
        k.append(((i2,p[i2]),(i1,p[i1])))
        point += p[i1]
    else:
        k.append(((i1,p[i1]),(i2,p[i2])))
        point += p[i2]
# print(k)
# print(point)

for len in range(3,n+1):
    for i1 in range(n-len+1):
        set1=k[i1]
        set2=k[i1+1]
        # print(set1,set2)
        if set1 == set2: # Set1 and Set2 is equal
            pass
            # print("The same")
        elif set1[0] == set2[0]: # MAX#1 is the same. MAX#2 should be different. 
            if set1[1][1] > set2[1][1]: # second max of set1 should be the second max of the new set
                pass
            #    print("same2")
            else: # sedcond max of set2 should be the second max of the new set
                k[i1]=(set1[0],set2[1])
        elif set1[0][1] > set2[0][1]: 
            if set1[1][1] > set2[0][1]: # MAX1 of set1 should be the  MAX1 of the new set 
                pass
            #    print("same2")
            else: 
                k[i1]=(set1[0],set2[0])
        else:
            if set1[0][1] > set2[1][1]: # MAX1 of set1 should be the  MAX1 of the new set 
                k[i1]=(set2[0],set1[0])
            else: 
                k[i1]=set2
        point += k[i1][1][1]
    del k[-1]
    #print(k)    
    #print(point)

print(point)
exit(0)
    
print(s)

exit(0)

i = 0
# print(a)
while True:
	b = list(map(lambda x : x & 0b1, a))
	# print(b)
	c = max(b)
	# print(c)
	if c > 0:
		break

	a = list(map(lambda x : x >> 1, a))
	# print(a)
	i += 1

print(i)
exit()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
 
P = list(map(int, input().split()))
 
import heapq
my_list = []
sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        my_list = P[i:j+1]
        my_list = [-i for i in my_list]
        heapq.heapify(my_list)
        heapq.heappop(my_list)
        sum += -min(my_list)
 
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n = int(input())
li = [-1 * int(i) for i in input().split()]
ans = 0

for a in range(len(li)):
  li2 = li[a:]
  for b in range(len(li2)):
    li3 = li2[:b+1]
    li4 = heapq.heapify(li3)
    if len(li3) >= 2:
      heapq.heappop(li3)
      ans += ((-1)*heapq.heappop(li3))

print(ans)

Submission status: Time Limit Exceeded

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


#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:
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)
        A.insert(index, 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 = [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):
        mat[l][max(i1, i2):r + 1] = [ret] * (r + 1 - max(i1, i2))
    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()))

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 = 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):
            top = int(P[i])
            second = 0
            for j in range(i+1, N):
                if int(P[j]) > top:
                    second = top
                    top = int(P[j])
                elif int(P[j]) > second:
                    second = int(P[j])
                ans += second
        print(ans)

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):
    ichi = p[l]
    ni = 0
    for i in range(1,(n+1-l)):
        if p[l+i] > ichi:
            ni = ichi
            ichi = p[l+i]
        elif p[l+i] <= ichi and p[l+i] >ni:
            ni = p[l+i]
        ans += ni
#        print(str(l) + ","+str(l+i)+ ","+str(ichi)+ ","+str(ni))

print(ans)