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:
#E

#二分探索を導入
n = int(input())
p = list(map(int,input().split()))

ans = 0

d_ind = [-1,-1,n,n]
s = [-1,-1]
t = [n,n]

for i in range(n):
    j = n-i#n,n-1,n-2,,,,1の順で調べる
    j_ind = p.index(j)
    sl = 0
    sr = len(d_ind)-1
    while sr-sl > 1:
        m = (sr + sl)//2
        if d_ind[m]>j_ind:
            sr = m
        else:
            sl = m
    #二分探索でd_indの中でjの位置がどのか探した。
    #d_indはjより大きな数字のインデックスの集まり（昇順にならべたある）
    k = sr
    s = d_ind[:k]
    t = d_ind[k:]
    l1 = s[-1]
    l2 = s[-2]
    r1 = t[0]
    r2 = t[1]
    ans += ((r1-j_ind)*(l1-l2)+(r2-r1)*(j_ind-l1))*j
    d_ind.insert(k,j_ind)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E

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

ans = 0

d_ind = [-1,-1,n,n]
s = [-1,-1]
t = [n,n]

for i in range(n):
    j = n-i#n,n-1,n-2,,,,1の順で調べる
    j_ind = p.index(j)
    for k in range(len(d_ind)):
        if d_ind[k] > j_ind:
            s = d_ind[:k]
            t = d_ind[k:]
            l1 = s[-1]
            l2 = s[-2]
            r1 = t[0]
            r2 = t[1]
            ans += ((r1-j_ind)*(l1-l2)+(r2-r1)*(j_ind-l1))*j
            d_ind.insert(k,j_ind)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E

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

ans = 0

for i in range(1,n):
    #nはなくてよい
    l_ko = 0
    r_ko = 0
    l2 = -1
    r2 = n

    i_index = p.index(i)
    r1 = i_index
    l1 = i_index
    for j in range(1,i_index+1):
        if p[i_index-j] > i:
            l1 = i_index-j
            l_ko = 1
            break
    for k in range(1,l1+1):
        if p[l1-k] > i:
            l2 = l1-k
            l_ko = 2
            break
    for l in range(1,n-i_index):
        if p[i_index+l] > i:
            r1 = i_index+l
            r_ko = 1
            break
    for m in range(1,n-r1):
        if p[r1+m] > i:
            r2 = r1+m
            r_ko = 2
            break
    if l_ko == 0 and r_ko != 0:
        ans += (r2-r1)*(i_index+1)*i
    elif l_ko != 0 and r_ko == 0:
        ans += (l1-l2)*(n-i_index)*i
    elif l_ko == 0 and r_ko == 0:
        ans += 0
    else:
        ans += ((r1-i_index)*(l1-l2)+(r2-r1)*(i_index-l1))*i
#    print(str(i) + "," + str(ans)+ "," + str(l1)+ "," + str(l2)+ "," + str(r1)+ "," + str(r2))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

sys.setrecursionlimit(5 * 10**5)
input=sys.stdin.readline

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

index = [0] * N
for i, p in enumerate(P):
    index[N-p] = i

bigger = []

ans = 0

def count(ja, jb):
    a = bigger[ja]
    b = bigger[jb]

    if ja >= 1:
        mi = bigger[ja-1] + 1
    else:
        mi = 0

    if jb <= len(bigger) - 2:
        ma = bigger[jb+1] - 1
    else:
        ma = N - 1

    return (a - mi + 1) * (ma - b + 1)

for i in index:
    j = bisect.bisect_left(bigger, i)
    bigger.insert(j, i)

    if j >= 1:
        ans += count(j-1, j) * P[i]

    if j <= len(bigger) - 2:
        ans += count(j, j+1) * P[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP =[int(i) for i in input().split()]
#n = 10000
#ListP = [i for i in range(n)]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
#ListTPos = [0] * (n+2) + [n+1, n+1]
ListTPos = [0] * (n + 1) + [n+1]
ListTPos[ListPos2[n]] = ListPos2[n]
pos = 0
for i in reversed(range(1,n)):
	posi = ListPos2[i]
	ListTPos[posi] =  posi
	for j in ListTPos[posi+1:]:
		if (j > 0):
			pos = ListPos.index(j)
			ListPos.insert(pos, posi)
			#pos = ListTPos[j]
			break
	l1 = ListPos[pos-1]
	l2 = ListPos[pos-2]
	h1 = ListPos[pos+1]
	h2 = ListPos[pos+2]
	points += i * ((posi-l1)*(h2-h1) + (h1-posi)*(l1-l2))
	#low1 = ListPos[pos] - ListPos[pos-1]
	#low2 = ListPos[pos-1] - ListPos[pos-2]
	#high1 = ListPos[pos+1] - ListPos[pos]
	#high2 = ListPos[pos+2] - ListPos[pos+1]
	#points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

sys.setrecursionlimit(5 * 10**5)
input=sys.stdin.readline

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

index = list(range(N))
index.sort(key=lambda x:P[x], reverse=True)

bigger = []

ans = 0

def count(ja, jb):
    a = bigger[ja]
    b = bigger[jb]

    if ja >= 1:
        mi = bigger[ja-1] + 1
    else:
        mi = 0

    if jb <= len(bigger) - 2:
        ma = bigger[jb+1] - 1
    else:
        ma = N - 1

    return (a - mi + 1) * (ma - b + 1)

for i in index:
    j = bisect.bisect_left(bigger, i)
    bigger.insert(j, i)

    if j >= 1:
        ans += count(j-1, j) * P[i]

    if j <= len(bigger) - 2:
        ans += count(j, j+1) * P[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
 
sum_result = 0
for L in range(N - 1):
  if P[L] > P[L+1]:
    first, second = P[L : L+2]
  else:
    second, first = P[L : L+2]
  sum_result += second
  for R in range(L + 2, N):
    if P[R] > first:
      second = first
      first = P[R]
    elif P[R] > second:
      second = P[R]
    sum_result += second
print(sum_result)

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:
n = int(input())
P = list([int(x) for x in input().split()])
P_i = sorted(range(len(P)), key=lambda k: P[k], reverse=True)
S = {0, n+1}
T = list(i for i in range(n+2))
ans = 0

for i in P_i:
    S1 = T[0:i+1]
    l1 = sorted(S.intersection(S1))[-1]
    if l1 == 0:
        l2 = 0
    else:
        l2 = sorted(S.intersection(S1))[-2]
    h1 = sorted(S.difference(S1))[0]
    if h1 == n+1:
        h2 = n+1
    else:
        h2 = sorted(S.difference(S1))[1]
    ans += P[i] * ((l1-l2)*(h1-(i+1)) + (i+1-l1)*(h2-h1))
    S.add(i+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
P = list([int(x) for x in input().split()])
P_i = sorted(range(len(P)), key=lambda k: P[k], reverse=True)
S = list([0, 0, n+1, n+1])
ans = 0

for i in P_i:
    low = list(filter(lambda x: x < i+1, S))
    high = list(filter(lambda x: x > i+1, S))
    l1 = sorted(low)[-1]
    l2 = sorted(low)[-2]
    h1 = sorted(high)[0]
    h2 = sorted(high)[1]
    ans += P[i] * ((l1-l2)*(h1-(i+1)) + (i+1-l1)*(h2-h1))
    S.append(i+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class RedBlackTree:
    # For performance, nodes are implemented as lists.
    #   [left, right, data, color, count]
    #   color: 1:RED  0:BLACK
    #
    # It is useful to set the left/right index to 0/1 for boolean access.
    #
    # The end nodes are BLACK and of which value is EOT (End Of Tree).

    def __init__(self, EOT=-1):
        self.EOT = EOT
        self.root = self._leaf()

    def _leaf(self):
        return [None, None, self.EOT, 0, 0]

    def _rotate(self, node, r):
        child = node[r ^ 1]
        node[r ^ 1] = child[r]
        child[r] = node
        child[3] = node[3]
        node[3] = 1
        child_count = child[4]
        child[4] = node[4]
        node[4] -= child_count - node[r ^ 1][4]
        return child

    def insert(self, x):
        stack = []
        node = self.root
        while node[2] != self.EOT:
            # Variation: If the same value is not allowed, return when found.

            to_right = x >= node[2]
            stack.append((node, to_right))
            node = node[to_right]

        # Insert values to the end node
        node[0] = self._leaf()
        node[1] = self._leaf()
        node[2] = x
        node[3] = 1
        node[4] = 1

        # Increase count
        for parent, _ in stack:
            parent[4] += 1

        # Validate tree and rotate if needed.
        while stack:
            parent, r = stack.pop()
            if parent[3] == 1:
                node = parent
                continue
            parent[r] = node
            node, flag = self._balance_insert(parent, r)

            if stack and flag == True:
                parent, r = stack.pop()
                parent[r] = node
                break

        else:
            # If the root might have changed, update its color.
            self.root = node
            self.root[3] = 0

    def _balance_insert(self, node, r):
        flag = True
        if node[r][r ^ 1][3] == 1:
            node[r] = self._rotate(node[r], r)
        if node[r][r][3] == 1:
            if node[r ^ 1][3] == 1:
                node[3] = 1
                node[r ^ 1][3] = node[r][3] = 0
                flag = False
            else:
                node = self._rotate(node, r ^ 1)
        return node, flag

    def delete(self, x):
        node = self.root
        stack = []
        while node[2] != x:
            r = node[2] < x
            stack.append((node, r))
            node = node[r]

        # Not Found
        if node[2] == self.EOT:
            return

        # Node has 2 children: swap min node in right tree and delete min node
        if node[0][2] != self.EOT and node[1][2] != self.EOT:
            stack.append((node, 1))
            min_node = self.get_min(node[1], stack)
            node[2] = min_node[2]
            node = min_node

        # Decrease count
        for parent, _ in stack:
            parent[4] -= 1

        # Node has 0/1 child
        parent, r = stack[-1]
        if node[0][2] == self.EOT:
            parent[r] = node[1]
            node[1][3] = 0
            # Balance is only needed if both children are EOT and self color is black.
            if node[1][2] != self.EOT or node[3] == 1:
                return
        elif node[1][2] == self.EOT:
            parent[r] = node[0]
            node[0][3] = 0
            return

        # Validate tree and rotate if needed.
        while stack:
            parent, r = stack.pop()
            node, flag = self._balance_delete(parent, r)

            if stack and flag == True:
                parent, r = stack.pop()
                parent[r] = node
                break
        else:
            # If the root might have changed, update its color.
            self.root = node
            self.root[3] = 0

    def get_min(self, node, stack):
        while node[0][2] != self.EOT:
            stack.append((node, 0))
            node = node[0]
        return node

    def _balance_delete(self, node, r):
        if node[r ^ 1][r][3] == 0 and node[r ^ 1][r ^ 1][3] == 0:
            if node[r ^ 1][3] == 0:
                node[r ^ 1][3] = 1
                if node[3] == 0:
                    return node, False
                node[3] = 0
            else:
                node = self._rotate(node, r)
                node[r], _ = self._balance_delete(node[r], r)
        else:
            if node[r ^ 1][r][3] == 1:
                node[r ^ 1] = self._rotate(node[r ^ 1], r ^ 1)
            node = self._rotate(node, r)
            node[r][3] = 0
            node[r ^ 1][3] = 0
        return node, True

    def upper_bound(self, x):
        """
        :return Smallest y satisfying x < y and its leftmost index.
                If not exists, (EOT, length) will be returned.
        """
        node = self.root
        y = self.EOT
        i = node[4]
        j = 0
        while node[2] != self.EOT:
            if x < node[2]:
                y = node[2]
                i = j + node[0][4]
                node = node[0]
            else:
                j += node[0][4] + 1
                node = node[1]
        return y, i

    def lower_bound(self, x):
        """
        :return Smallest y satisfying x <= y and its leftmost index.
                If not exists, (EOT, length) will be returned.
        """
        node = self.root
        y = self.EOT
        i = node[4]
        j = 0
        while node[2] != self.EOT:
            if x <= node[2]:
                y = node[2]
                i = j + node[0][4]
                node = node[0]
            else:
                j += node[0][4] + 1
                node = node[1]
        return y, i

    def get_by_index(self, i):
        """
        :return (0-indexed) i-th smallest item.
                If i is greater than length, EOT will be returned.
        """
        node = self.root
        if node[4] <= i:
            return self.EOT
        j = i
        while node[2] != self.EOT:
            left_count = node[0][4]
            if left_count == j:
                return node[2]
            elif left_count > j:
                node = node[0]
            else:
                j -= left_count + 1
                node = node[1]

    def debug_print(self):
        self._debug_print(self.root, 0)

    def _debug_print(self, node, depth):
        if node[2] != self.EOT:
            self._debug_print(node[0], depth + 1)
            print('      ' * depth, 'BR'[node[3]], node[2], node[4])
            self._debug_print(node[1], depth + 1)


n = int(input())
ppp = list(map(int, input().split()))
pps = list(enumerate(ppp))
pps.sort(reverse=True, key=itemgetter(1))

rbt = RedBlackTree(-2)
rbt.insert(-1)
rbt.insert(-1)
rbt.insert(n)
rbt.insert(n)

ans = 0
for i, p in pps:
    r1, j = rbt.upper_bound(i)
    r2 = rbt.get_by_index(j + 1)
    l1 = rbt.get_by_index(j - 1)
    l2 = rbt.get_by_index(j - 2)
    ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
    rbt.insert(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(i) for i in input().split()]
print(sum([sorted([P[i] for i in range(L - 1, R)])[-2] for L in range(1, N) for R in range(L + 1, N + 1)]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(i) for i in input().split()]
summa = 0
for L in range(1, N):
    for R in range(L + 1, N + 1):
        a = sorted([P[i] for i in range(L - 1, R)])
        summa += a[-2]
print(summa)

Submission status: Time Limit Exceeded

Solution code:


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

idx = [0] * (N+3)
cnt = 1
for a in A:
    idx[a] = cnt
    cnt += 1
idx[N+1] = N+1
idx[N+2] = 0

sets = [0,N+1]

ans = 0
import bisect
for i in reversed(range(1,N+1)):
    index = idx[i]
    tmplist = sets
    L = len(tmplist)
    left1 = max(bisect.bisect_left(tmplist,index)-1, 0)
    left2 = max(left1-1,0)
    right1 = min(bisect.bisect_left(tmplist,index), L-1)
    right2 = min(right1+1, L-1)
    
    l1 = tmplist[left1]
    l2 = tmplist[left2]
    r1 = tmplist[right1]
    r2 = tmplist[right2]
    ans += i * ((r1-index)*(l1-l2) + (index-l1)*(r2-r1))
    insert_index = bisect.bisect_left(tmplist,index)
    sets = tmplist[:insert_index] + [index] + tmplist[insert_index:]
    
    
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):
        ans += sorted(p[i:j+1])[-2]
print(ans)

Submission status: Time Limit Exceeded

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

import bisect

N = int(input())
P = list(map(int, input().split()))
index = [0]*(N+1)
for i in range(N):
    index[P[i]] = i

max_list = []
max_list.append(-1)
max_list.append(N)

ans=0
for i in reversed(range(1,N+1)):
    bisect.insort_right(max_list,index[i])
    x = bisect.bisect_left(max_list,index[i])
    l = []
    r = []
    tmp = x
    for j in range(2):
        if tmp==0: break
        tmp-= 1
        l.append(max_list[tmp])
    tmp = x
    for j in range(2):
        if max_list[tmp]==max_list[-1]: break
        tmp+=1
        r.append(max_list[tmp])
    ls = []
    rs = []
    ls.append(max_list[x]-l[0])
    rs.append(r[0]-max_list[x])
    c=0
    if len(r) == 2:
        rs.append(r[1]-r[0])
        c+=ls[0]*rs[1]
    if len(l) == 2: 
        ls.append(l[0]-l[1])
        c+=ls[1]*rs[0]
    ans+=i*c

print(ans)

Submission status: Time Limit Exceeded

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

import bisect

N = int(input())
P = list(map(int, input().split()))
index = [0]*(N+1)
for i in range(N):
    index[P[i]] = i

max_list = []
max_list.append(-1)
max_list.append(N)

ans=0
for i in reversed(range(1,N+1)):
    bisect.insort_right(max_list,index[i])
    x = bisect.bisect_left(max_list,index[i])
    l = []
    r = []
    tmp = x
    for j in range(2):
        if tmp==0: break
        tmp-= 1
        l.append(max_list[tmp])
    tmp = x
    for j in range(2):
        if max_list[tmp]==max_list[-1]: break
        tmp+=1
        r.append(max_list[tmp])
    ls = []
    rs = []
    ls.append(max_list[x]-l[0])
    rs.append(r[0]-max_list[x])
    c=0
    if len(r) == 2:
        rs.append(r[1]-r[0])
        c+=ls[0]*rs[1]
    if len(l) == 2: 
        ls.append(l[0]-l[1])
        c+=ls[1]*rs[0]
    ans+=i*c

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
area = list(reversed(range(1,n)))
for i in area:
	ListPos.append(ListPos2[i])
	ListPos.sort()
	pos = ListPos.index(ListPos2[i])
	lh = ListPos[pos]
	l1 = ListPos[pos-1]
	l2 = ListPos[pos-2]
	h1 = ListPos[pos+1]
	h2 = ListPos[pos+2]
	points += i * ((lh-l1)*(h2-h1) + (h1-lh)*(l1-l2))
	#low1 = ListPos[pos] - ListPos[pos-1]
	#low2 = ListPos[pos-1] - ListPos[pos-2]
	#high1 = ListPos[pos+1] - ListPos[pos]
	#high2 = ListPos[pos+2] - ListPos[pos+1]
	#points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
import random
import bisect
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class BIT:
    '''
    BinaryIndexedTreeのクラス。0-indexed に統一してあるので0からn-1までの配列と思って使える。

    Parameters
    ----------
        n (Union(int, list)): int なら使う BIT のサイズ。list ならそのlistで BIT を初期化する
    '''
    def __init__(self, x, d=0):
        if isinstance(x, int):
            self.size = x
            self.tree = [d for _ in range(self.size + 1)]
        elif isinstance(x, list):
            self.size = len(x)
            self.tree = [d for _ in range(self.size + 1)]
            self.build(x)
        else:
            raise TypeError

    def build(self, arr):
        """
        初期化されたあとのBITをリストの値に設定する

        Parameters
        ----------
            arr (list): 元のlsit

        Raises
        ------
            TypeError: 入力はlistでないといけないことに注意してください。
        """
        if not isinstance(arr, list):
            raise TypeError
        for num, x in enumerate(arr):
            self.add(num, x)

    def sum(self, i):
        '''[0,i) の和'''
        if i < 0:
            return 0
        s = self.tree[0]
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
        return s

    def add(self, i, a):
        i += 1
        '''i番目の要素にaを足す'''
        if(i == 0):
            return
        while (i <= self.size):
            self.tree[i] += a
            i += (i & -i)

    def lower_bound(self, w):
        '''[0,i]の和 >= w をみたす最小の index
        Examples
        ----------
        >>> bit = BIT([1,0,0,1,0,1,0])
        >>> bit.lower_bound(1)
        0
        >>> bit.lower_bound(2)
        3
        >>> bit.lower_bound(3)
        5
        '''
        if w <= 0:
            return -1
        x = 0
        k = 1 << (self.size.bit_length() - 1)
        while k:
            if x + k <= self.size and self.tree[x + k] < w:
                w -= self.tree[x + k]
                x += k
            k >>= 1
        return x

    def getKthNum(self, w):
        '''k番目(k = 0, 1, ...)に小さい数を返す'''
        w += 1
        return self.lower_bound(w)

    def upper_bound(self, w):
        w += 0.00000000001
        return self.lower_bound(w)

    def query(self, l, r):
        '''[l, r)の和を求める
        >>> bit = BIT([1,2,3,4,5])
        >>> bit.query(1,4)
        9
        >>> bit.query(0,2)
        3
        '''
        return self.sum(r) - self.sum(l)

    # 出力関係（デバッグのみに用いる）
    def __getitem__(self, item):
        if not isinstance(item, int):
            _tmp = item.indices(self.size + 1)
            return [self.sum(i + 1) - self.sum(i) for i in range(_tmp[0], _tmp[1], _tmp[2])]
        else:
            return self.sum(item + 1) - self.sum(item)
    def __str__(self):
        return str(self[0:self.size])
# END CUT HERE

class sqrtDecomposition():
    def __init__(self, N):
        self.BASE = 100
        self.size = 0
        self.a = [[] for i in range(ceil(N / self.BASE))]
        self.b = BIT(ceil(N / self.BASE))

    def insert(self, i):
        self.size += 1
        idx = bisect.bisect_left(self.a[i // self.BASE], i)
        self.a[i // self.BASE].insert(idx, i)
        self.b.add(i // self.BASE, 1)
        return idx + self.b.sum(i // self.BASE)

    def _next(self, key, idx1, idx2):
        if len(self.a[idx1]) - 1 == idx2:
            idx = self.b.lower_bound(key + 1)
            return (idx, 0)
        else:
            return (idx1, idx2 + 1)

    def get(self, left, right):
        left += 1
        right += 1
        idx1, idx2 = None, None
        for key in range(left, right):
            # debug(key, self.size)
            if key <= 0 or key > self.size:
                yield (None, None)
                continue
            if not idx1:
                idx1 = self.b.lower_bound(key)
                idx2 = key - self.b.sum(idx1) - 1
            else:
                idx1, idx2 = self._next(key - 1, idx1, idx2)
            yield (idx1, idx2)

def main():
    N = ii()
    # N = 10**6
    t = sqrtDecomposition(N)
    # P = [i for i in range(N)]
    # random.shuffle(P)
    P = lmi()
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    # debug(L)
    ans = 0
    for num, i in enumerate(L):
        idx = t.insert(i)
        # debug(idx)
        g = t.get(idx - 2, idx + 3)
        l = [-1] * 5
        for idx in range(5):
            idx1, idx2 = next(g)
            # debug(idx1, idx2)
            if idx == 2:
                continue
            if idx < 2 and idx1 is None:
                l[idx] = -1
            elif idx > 2 and idx1 is None:
                l[idx] = N
            else:
                l[idx] = t.a[idx1][idx2]

        # debug(l[0], l[1], l[3], l[4])
        ans += (abs(i - l[1]) * abs(l[4] - l[3]) + abs(l[1] - l[0]) * abs(l[3] - i)) * (N - num)
    print(ans)
    return


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
        import cProfile
        cProfile.run('main()', sort=1)
    else:
        main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
#print(ListPos2)
SetPos = {ListPos2[n]}
for i in reversed(range(1, n)):
	SetPos.add(ListPos2[i])
	ListPos = [0, 0] + sorted(SetPos) + [n+1, n+1]
	pos = ListPos.index(ListPos2[i])
	#print(SetDiff)
	#print(SetPos-SetDiff)
	#print(pos)
	#print(ListPos)
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
#print(ListPos2)
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
for i in reversed(range(1, n)):
	SetPos = set(ListPos)
	SetDiff = set(range(0, ListPos2[i]))
	pos = ListPos.index(min(SetPos - SetDiff))
	ListPos.insert(pos, ListPos2[i])
	#print(SetDiff)
	#print(SetPos-SetDiff)
	#print(pos)
	#print(ListPos)
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
P = list([int(x) for x in input().split()])
S = list([0, 0, n+1, n+1])
ans = 0

for i in range(1,n+1)[::-1]:
  
    Pi = P.index(i)+1
    low = list(filter(lambda x: x < Pi, S))
    high = list(filter(lambda x: x > Pi, S))
    
    l1 = sorted(low)[-1]
    l2 = sorted(low)[-2]
    h1 = sorted(high)[0]
    h2 = sorted(high)[1]
    
    ans += i * ((l1-l2)*(h1-Pi) + (Pi-l1)*(h2-h1))
    S.append(Pi)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect


class SqrtSet:
    def __init__(self, block_limit=300):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret

    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            block = block[:sep]


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = SqrtSet()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Submission status: Time Limit Exceeded

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

for i in range(N):
    max_value1 = 0
    max_value2 = 0
    for j in range(i, N):
        if P[j] > max_value1:
            max_value2 = max_value1
            max_value1 = P[j]
        elif P[j] > max_value2:
            max_value2 = P[j]
        sum_X += max_value2
        
print(sum_X)