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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, input().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
ans = 0
for i,p in Pn[1:]:
  cnt = 0
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    cnt += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    cnt += l*r
  ans += cnt*p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, input().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
Cn = [0 for _ in range(N+1)]
for i,p in Pn[1:]:
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    Cn[p] += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    Cn[p] += l*r

ans = 0
for i,c in enumerate(Cn):
  ans += i*c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def binarySearch(lst, key):
    left = 0;
    right = len(lst)-1;
    while True:
        middle = left + (right - left)//2;
        value = lst[middle]
        if value == key:
            return middle
        elif value < key:
            left = middle + 1
        else:
            right = middle - 1
        if right < left:
          return  middle if left < middle else left

N = int(input());
P = [int(s) for s in input().split()]

Q = [0]*(N+1)

for i, p in enumerate(P):
    Q[p] = i

r = [-1, -1, N, N]
ans = 0

for v in range(N, 0, -1):
  i = Q[v]
  j = binarySearch(r, i)
  w = r[j-2]
  x = r[j-1]
  y = r[j]
  z = r[j+1]
  c = (x-w)*(y-i) + (i-x)*(z-y)
  r.insert(j, i)
  ans += v*c
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
idx = [0]*(n+1)
for i in range(n):
	idx[p[i]]=i

from bisect import bisect,insort
q=[-1,n]
ans=0
for i in range(n,0,-1):
	tidx=idx[i]
	t=bisect(q,tidx)
	if t!=1:
		ans+=(q[t-1]-q[t-2])*(q[t]-tidx)*i
	if t!=len(q)-1:
		ans+=(tidx-q[t-1])*(q[t+1]-q[t])*i
	insort(q,tidx)
print(ans)

Submission status: Time Limit Exceeded

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

vec = [(P[i], i) for i in range(N)]
vec.sort(reverse=True)

ans = 0
for i in range(1, len(vec)):
    L = [-1]
    R = []
    for j in range(i):
        if vec[j][1] < vec[i][1]:
            L.append(vec[j][1])
        elif vec[j][1] > vec[i][1]:
            R.append(vec[j][1])
    R.append(N)
    R.sort()
    L.sort()

    if len(L) > 1:
        ans += vec[i][0] * (L[-1] - L[-2]) * (R[0] - vec[i][1])
    if len(R) > 1:
        ans += vec[i][0] * (vec[i][1] - L[-1]) * (R[1] - R[0])

print(ans)

Submission status: Time Limit Exceeded

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

ans = []
for i in range(0, (len(a)-1)):
    for j in range(i+1, len(a)):
        b = a[i:j+1]
        b.sort()
        ans.append(b[-2])

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N = int(input())
    P = list(map(int, input().split()))
    x = 0

    for l in range(0, N-1):
        for r in range(l+1, N):
            temp = sorted(P[l:r+1])[-2]
##            print('l:{} r:{} temp:{}'.
##                  format(l, r, temp))
            x += temp
    print(x)

Submission status: Time Limit Exceeded

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

sum = 0
for i in range(N - 1):
  max = 0
  s_max = 0
  for j in range(N - i):
    if max == 0:
      max = int(P[j + i])
    elif max < int(P[j + i]):
      s_max = max
      max = int(P[j + i])
    elif max > int(P[j + i]) and s_max < int(P[j + i]):
      s_max = int(P[j + i])
      
    if j > 0:
      sum = sum + s_max

print(sum)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    L = [-1] + [j for j in range(i) if P[i] < P[j]]
    R = [j for j in range(i + 1, N) if P[i] < P[j]] + [N]

    if len(L) > 1:
        ans += P[i] * (L[-1] - L[-2]) * (R[0] - i)
    if len(R) > 1:
        ans += P[i] * (i - L[-1]) * (R[1] - R[0])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N = int(sys.stdin.readline())
list_p = list(map(int, sys.stdin.readline().split()))

sum_2nd = 0

for i in range(N-1):
    max1 = list_p[i]
    max2 = 0
    for j in range(i, N-1):
        if(list_p[j+1] > max1):
            max2 = max1
            max1 = list_p[j+1]
        elif(list_p[j+1] > max2):
            max2 = list_p[j+1]

        # print(max1, max2)
        sum_2nd += max2

print(sum_2nd)




# sum_n = 0

# for i in range(N-1):
#     sum_n += i+1

# sum_n = sum_n * (N-1)
# sum_d = 0

# for i in range(N-2):
#     sum_d +=(i+1) * (N - i - 2)

# ans = sum_n - sum_d

# print(sum_n)
# print(sum_d)
# print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def f(Q):
    if len(Q)==2:
        return min(Q)
    else:
        s = 0
        r = Q.popleft()
        Max = r
        second_Max = 0
        for q in Q:
            if q>Max:
                second_Max = Max
                Max = q
            elif second_Max<q<=Max:
                second_Max = q
            s += second_Max
        return(f(Q) + s)
    
N = int(input())
P = deque(list(map(int, input().split())))
print(f(P))

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    P = list(map(int, input().split()))
    # 方針：自分(x)より大きい数字をちょうど1個含む範囲を考える(解説の通り)
    idx = [0]*(N+1)
    for i,p in enumerate(P):
        idx[p] = i # 数列 P の値 p のインデックス
    a = [] # 処理済みのインデックスのリスト。ソートしてidx[x]の隣をbisectで探す
    ans = 0
    for x in range(N,0,-1): # N,N-1,..,1
        l2 = l1 = -1 # x よりも大きい数のインデックス。見つからなかった場合は範囲外(-1). l2,..l1,..x
        i = bisect.bisect_left(a, idx[x])
        if i > 0:
            l1 = a[i-1]
        if i > 1:
            l2 = a[i-2]
        r1 = r2 = N # 同上。x,..r1,..r2
        i = bisect.bisect_right(a, idx[x])
        if i <= N and len(a) > i:
            r1 = a[i]
        if i <= N-1 and len(a) > i+1:
            r2 = a[i+1]
        bisect.insort(a, idx[x])

        r = l = 0
        if r1 != N: # 右で
            r = (idx[x]-l1)*(r2-r1)
        if l1 != -1: # 左で
            l = (l1-l2)*(r1-idx[x])
#        print(x,":",l2,l1,idx[x],r1,r2, "=>", r,l)
        ans += x*(r+l)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    P = list(map(int, input().split()))
    # 方針：自分(x)より大きい数字をちょうど1個含む範囲を考える(解説の通り)
    idx = [0]*(N+1)
    for i,p in enumerate(P):
        idx[p] = i # 数列 P の値 p のインデックス
    a = [] # 処理済みのインデックスのリスト。ソートしてidx[x]の隣をbisectで探す
    ans = 0
    for x in range(N,0,-1): # N,N-1,..,1
        l2 = l1 = -1 # x よりも大きい数のインデックス。見つからなかった場合は範囲外(-1). l2,..l1,..x
        i = bisect.bisect_left(a, idx[x])
        if i > 0:
            l1 = a[i-1]
        if i > 1:
            l2 = a[i-2]
        r1 = r2 = N # 同上。x,..r1,..r2
        i = bisect.bisect_right(a, idx[x])
        if i <= N and len(a) > i:
            r1 = a[i]
        if i <= N-1 and len(a) > i+1:
            r2 = a[i+1]
        a.append(idx[x])
        a.sort()

        r = l = 0
        if r1 != N: # 右で
            r = (idx[x]-l1)*(r2-r1)
        if l1 != -1: # 左で
            l = (l1-l2)*(r1-idx[x])
#        print(x,":",l2,l1,idx[x],r1,r2, "=>", r,l)
        ans += x*(r+l)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
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
from random import shuffle
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('text.txt', 'r')
#     sys.stdin = fin
# local only
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 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

class RBNode:
    def __init__(self, val, is_red, parent=None, left=None, right=None):
        self.val = val
        self.parent = parent
        self.left = left
        self.right = right
        self.color = is_red


class RBTree:
    def __init__(self):
        self.root = None

    def left_rotate(self, node):
        # set the node as the left child node of the current node's right node
        right_node = node.right
        if right_node is None:
            return
        else:
            # right node's left node become the right node of current node
            node.right = right_node.left
            if right_node.left is not None:
                right_node.left.parent = node
            right_node.parent = node.parent
            # check the parent case
            if node.parent is None:
                self.root = right_node
            elif node is node.parent.left:
                node.parent.left = right_node
            else:
                node.parent.right = right_node
            right_node.left = node
            node.parent = right_node

    def right_rotate(self, node):
        # set the node as the right child node of the current node's left node
        left_node = node.left
        if left_node is None:
            return
        else:
            # left node's right  node become the left node of current node
            node.left = left_node.right
            if left_node.right is not None:
                left_node.right.parent = node
            left_node.parent = node.parent
            # check the parent case
            if node.parent is None:
                self.root = left_node
            elif node is node.parent.left:
                node.parent.left = left_node
            else:
                node.parent.right = left_node
            left_node.right = node
            node.parent = left_node

    def insert(self, node):
        # the inserted node's color is default is red
        root = self.root
        insert_node_parent = None
        # find the position of inserted node
        while root is not None:
            insert_node_parent = root
            if insert_node_parent.val < node.val:
                root = root.right
            else:
                root = root.left
        # set the n ode's parent node
        node.parent = insert_node_parent
        if insert_node_parent is None:
            # case 1  inserted tree is null
            self.root = node
        elif insert_node_parent.val > node.val:
            # case 2 not null and find left or right
            insert_node_parent.left = node
        else:
            insert_node_parent.right = node
        node.left = None
        node.right = None
        node.color = 1
        # fix the tree to
        self.fix_insert(node)

    def fix_insert(self, node):
        # case 1 the parent is null, then set the inserted node as root and color = 0
        if node.parent is None:
            node.color = 0
            self.root = node
            return
            # case 2 the parent color is black, do nothing
        # case 3 the parent color is red
        while node.parent and node.parent.color == 1:
            if node.parent is node.parent.parent.left:
                uncle_node = node.parent.parent.right
                if uncle_node and uncle_node.color == 1:
                    # case 3.1 the uncle node is red
                    # then set parent and uncle color is black and grandparent is red
                    # then node => node.parent
                    node.parent.color = 0
                    node.parent.parent.right.color = 0
                    node.parent.parent.color = 1
                    node = node.parent.parent
                    continue
                elif node is node.parent.right:
                    # case 3.2 the uncle node is black or null, and the node is right of parent
                    # then set his parent node is current node
                    # left rotate the node and continue the next
                    node = node.parent
                    self.left_rotate(node)
                # case 3.3 the uncle node is black and parent node is left
                # then parent node set black and grandparent set red
                node.parent.color = 0
                node.parent.parent.color = 1
                self.right_rotate(node.parent.parent)
            else:
                uncle_node = node.parent.parent.left
                if uncle_node and uncle_node.color == 1:
                    # case 3.1 the uncle node is red
                    # then set parent and uncle color is black and grandparent is red
                    # then node => node.parent
                    node.parent.color = 0
                    node.parent.parent.left.color = 0
                    node.parent.parent.color = 1
                    node = node.parent.parent
                    continue
                elif node is node.parent.left:
                    # case 3.2 the uncle node is black or null, and the node is right of parent
                    # then set his parent node is current node
                    # left rotate the node and continue the next
                    node = node.parent
                    self.right_rotate(node)
                # case 3.3 the uncle node is black and parent node is left
                # then parent node set black and grandparent set red
                node.parent.color = 0
                node.parent.parent.color = 1
                self.left_rotate(node.parent.parent)
        self.root.color = 0

    def transplant(self, node_u, node_v):
        """
        replace u with v
        :param node_u: replaced node
        :param node_v:
        :return: None
        """
        if node_u.parent is None:
            self.root = node_v
        elif node_u is node_u.parent.left:
            node_u.parent.left = node_v
        elif node_u is node_u.parent.right:
            node_u.parent.right = node_v
        # check is node_v is None
        if node_v:
            node_v.parent = node_u.parent

    def find(self, key):
        node = self.root
        while node is not None:
            if node.val < key:
                node = node.right
            elif node.val > key:
                node = node.left
            else:
                return node
        return None

    def maximum(self, node):
        """
        find the max node when node regard as a root node
        :param node:
        :return: max node
        """
        temp_node = node
        while temp_node.right is not None:
            temp_node = temp_node.right
        return temp_node

    def minimum(self, node):
        """
        find the minimum node when node regard as a root node
        :param node:
        :return: minimum node
        """
        temp_node = node
        while temp_node.left:
            temp_node = temp_node.left
        return temp_node

    def search_higher(self, key, key_higher=None, node=None):
        if node is None:
            node = self.root
        if node.val is None:
            return key_higher
        if node.val > key:
            key_higher = node.val
            if node.left is None:
                return key_higher
            else:
                return self.search_higher(key, key_higher, node.left)
        if node.val < key:
            if node.right is None:
                return key_higher
            else:
                return self.search_higher(key, key_higher, node.right)
        # node.val == keyの場合
        if node.right is None:
            return key_higher
        else:
            if key_higher is None:
                return self.minimum(node.right).val
            else:
                return min(key_higher, self.minimum(node.right).val)

    def search_lower(self, key, key_lower=None, node=None):
        if node is None:
            node = self.root
        if node.val is None:
            return key_lower
        if node.val > key:
            if node.left is None:
                return key_lower
            else:
                return self.search_lower(key, key_lower, node.left)
        if node.val < key:
            key_lower = node.val
            if node.right is None:
                return key_lower
            else:
                return self.search_lower(key, key_lower, node.right)
        # node.val == keyの場合
        if node.left is None:
            return key_lower
        else:
            if key_lower is None:
                return self.maximum(node.left).val
            else:
                return max(key_lower, self.maximum(node.left).val)

    def delete(self, node):
        # find the node position
        node_color = node.color
        if node.left is None:
            temp_node = node.right
            self.transplant(node, node.right)
        elif node.right is None:
            temp_node = node.left
            self.transplant(node, node.left)
        else:
            # both child exits ,and find minimum child of right child
            node_min = self.minimum(node.right)
            node_color = node_min.color
            temp_node = node_min.right
            ##
            if node_min.parent != node:
                self.transplant(node_min, node_min.right)
                node_min.right = node.right
                node_min.right.parent = node_min
            self.transplant(node, node_min)
            node_min.left = node.left
            node_min.left.parent = node_min
            node_min.color = node.color
        # when node is black, then need to fix it with 4 cases
        if node_color == 0:
            self.delete_fixup(temp_node)

    def delete_fixup(self, node):
        # 4 cases
        while node != self.root and node.color == 0:
            # node is not root and color is black
            if node == node.parent.left:
                # node is left node
                node_brother = node.parent.right

                # case 1: node's red, can not get black node
                # set brother is black and parent is red
                if node_brother.color == 1:
                    node_brother.color = 0
                    node.parent.color = 1
                    self.left_rotate(node.parent)
                    node_brother = node.parent.right

                # case 2: brother node is black, and its children node is both black
                if (node_brother.left is None or node_brother.left.color == 0) and (
                        node_brother.right is None or node_brother.right.color == 0):
                    node_brother.color = 1
                    node = node.parent
                else:

                    # case 3: brother node is black , and its left child node is red and right is black
                    if node_brother.right is None or node_brother.right.color == 0:
                        node_brother.color = 1
                        node_brother.left.color = 0
                        self.right_rotate(node_brother)
                        node_brother = node.parent.right

                    # case 4: brother node is black, and right is red, and left is any color
                    node_brother.color = node.parent.color
                    node.parent.color = 0
                    node_brother.right.color = 0
                    self.left_rotate(node.parent)
                node = self.root
                break
            else:
                node_brother = node.parent.left
                if node_brother.color == 1:
                    node_brother.color = 0
                    node.parent.color = 1
                    self.left_rotate(node.parent)
                    node_brother = node.parent.right
                if (node_brother.left is None or node_brother.left.color == 0) and (
                        node_brother.right is None or node_brother.right.color == 0):
                    node_brother.color = 1
                    node = node.parent
                else:
                    if node_brother.left is None or node_brother.left.color == 0:
                        node_brother.color = 1
                        node_brother.right.color = 0
                        self.left_rotate(node_brother)
                        node_brother = node.parent.left
                    node_brother.color = node.parent.color
                    node.parent.color = 0
                    node_brother.left.color = 0
                    self.right_rotate(node.parent)
                node = self.root
                break
        node.color = 0

    def inorder(self):
        res = []
        if not self.root:
            return res
        stack = []
        root = self.root
        stack.append(root)
        while stack:
            root = stack.pop()
            res.append({'val': root.val, 'color': root.color})
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        # while root or stack:
        #     while root:
        #         stack.append(root)
        #         root = root.left
        #     root = stack.pop()
        #     res.append({'val': root.val, 'color': root.color})
        #     root = root.right
        return res



def main():
    N = ii()
    P = lmi()
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    ans = 0
    rb = RBTree()
    for num, i in enumerate(L):
        rb.insert(RBNode(i, 1))
        l1 = rb.search_lower(i, -1)
        l2 = rb.search_lower(l1, -1)
        r1 = rb.search_higher(i, N)
        r2 = rb.search_higher(r1, N)
        # print(l2, l1, r1, r2)
        ans += (abs(i - l1) * abs(r2 - r1) + abs(l1 - l2) * abs(r1 - i)) * (N - num)
    print(ans)
    return



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [int(i) for i in input().split()]
ans = 0
for i in range(n): #左端から
  if i==0: #一番左なら
    if p[i]==n:
      ans += 0
    elif p[i]==n-1:
      idx = p.index(n)
      ans += p[i]*(n-idx)
    else:
      idx = []
      for j in reversed(range(p[i]+1,n+1)):
        idx.append(p.index(j))
      idx.sort()
      temp = idx[1]-idx[0]
      ans += p[i]*temp
  elif i==n-1: #右端なら
    if p[i]==n:
      ans += 0
    elif p[i]==n-1:
      idx = p.index(n)
      ans += p[i]*(idx+1)
    else:
      idx = []
      for j in reversed(range(p[i]+1,n+1)):
        idx.append(p.index(j))
      idx.sort()
      temp = idx[-1] - idx[-2]
      ans += p[i]*temp
  else: #真ん中なら
    if p[i]==n:
      ans+=0
    elif p[i]==n-1:
      idx = p.index(n)
      chi = min(i,idx)
      ook = max(i,idx)
      temp = (chi+1)*(n-ook)
      ans += p[i]*temp
    else: #「大」が2つ以上あるとき
      left = p[:i]
      right = p[i+1:]
      if max(left)<p[i]: #小●大
        idx = []
        for j in range(i+1,n):
          if p[j]>p[i] and (len(idx)<2):
            idx.append(j)
          elif len(idx)==2:
            break
          else:
            idx = idx
        temp = (i+1)*(idx[1]-idx[0])
        ans += p[i]*temp
      elif max(right)<p[i]: #大●小
        idx = []
        for j in reversed(range(i)):
          if p[j]>p[i] and (len(idx)<2):
            idx.append(j)
          elif len(idx)==2:
            break
          else:
            idx = idx
        temp = (n-i)*(idx[0]-idx[1])
        ans += temp*p[i]
      else:
        idx_left = []
        for k in reversed(range(i)):
          if p[k]>p[i] and (len(idx_left)<2):
            idx_left.append(k)
          elif len(idx_left)==2:
            break
          else:
            idx_left = idx_left
        if len(idx_left)<2:
          idx_left.append(-1)
        idx_right = []
        for l in range(i+1,n):
          if p[l]>p[i] and (len(idx_right)<2):
            idx_right.append(l)
          elif len(idx_right)==2:
            break
          else:
            idx_right = idx_right
        if len(idx_right)<2:
          idx_right.append(n)
        temp_left = (idx_right[0]-i)*(idx_left[0]-idx_left[1])
        temp_right = (idx_right[1]-idx_right[0])*(i-idx_left[0])
        temp = temp_left+temp_right
        ans += p[i]*temp
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    P = list(map(int, input().split()))
    # 方針：自分(x)より大きい数字をちょうど1個含む範囲を考える(解説の通り)
    idx = [0]*(N+1)
    for i,p in enumerate(P):
        idx[p] = i # 数列 P の値 p のインデックス
    ans = 0
    for x in range(N,0,-1): # N,N-1,..,1
        l2 = l1 = -1 # x よりも大きい数のインデックス。見つからなかった場合は範囲外(-1). l2,..l1,..x
        for i in range(idx[x],-1,-1):
            if P[i] > x:
                if l1 == -1:
                    l1 = idx[P[i]]
                else:
                    l2 = idx[P[i]] 
                    break # l2 が見つかったらそれ以上探索しない…けどこれO(N^2)では…？
        r1 = r2 = N # x,..r1,..r2
        for i in range(idx[x],N,1):
            if P[i] > x:
                if r1 == N:
                    r1 = idx[P[i]]
                else:
                    r2 = idx[P[i]] # r2 が見つかったらそれ以上探索しない
                    break
        r = l = 0
        if r1 != N: # 右で
            r = (idx[x]-l1)*(r2-r1)
        if l1 != -1: # 左で
            l = (l1-l2)*(r1-idx[x])
#        print(x,":",l2,l1,idx[x],r1,r2, "=>", r,l)
        ans += x*(r+l)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def binary_search(cond, left_initial, right_initial):

    left = left_initial
    right = right_initial

    while left + 1 < right:
        mid = (left + right) // 2

        if cond(mid):
            right = mid
        else:
            left = mid

    return left


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve_e(n, p_list):
    ind_list = [0] * (n + 1)
    for i in range(n):
        ind_list[p_list[i]] = i + 1

    bit = Bit(n + 1)

    res = 0

    for i in range(n, 0, -1):
        ind = ind_list[i]
        bit.add(ind, 1)
        # right
        r1 = n + 1
        r2 = n + 1
        if bit.sum(n + 1) - bit.sum(ind) > 0:
            r1 = binary_search(lambda k: bit.sum(k) - bit.sum(ind) >= 1, ind, n + 1) + 1
        if bit.sum(n + 1) - bit.sum(ind) > 1:
            r2 = binary_search(lambda k: bit.sum(k) - bit.sum(ind) >= 2, ind, n + 1) + 1

        # left
        l1 = 0
        l2 = 0
        if bit.sum(ind) >= 2:
            l1 = binary_search(lambda k: bit.sum(ind) - bit.sum(k) <= 1, 0, ind) + 1
        if bit.sum(ind) >= 3:
            l2 = binary_search(lambda k: bit.sum(ind) - bit.sum(k) <= 2, 0, ind) + 1
        # print(l1, l2, r1, r2, ind, i)
        cnt = (ind - l1) * (r2 - r1) + (l1 - l2) * (r1 - ind)
        res += cnt * i

    return res


def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    print(solve_e(n, p_list))


if __name__ == "__main__":
    main()