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:
'''解説動画を見て実装'''
import bisect
N = int(input())
P = [int(x)-1 for x in input().split()]

idx = [None]*N

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

ans = 0
s = []  # ordered set をリストで代用 (bisect.insort で挿入)
sidx = []  # index for set
for x in range(N-1, -1, -1):
    i = idx[x]
    c = 0  # 組み合わせの個数
    bisect.insort(s, i)
    # print(s)
    lpos = [-1]*2  # x より左側で x より大きい数の位置
    rpos = [N]*2  # x より左側で x より大きい数の位置

    # 左側の探索
    it = s.index(i)  # iterator
    for j in range(2):
        if it == 0:
            break
        it -= 1
        lpos[j] = s[it]

    # 右側の探索
    it = s.index(i)  # iterator
    for j in range(2):
        it += 1
        if it == len(s):
            break
        rpos[j] = s[it]
    ls = (i-lpos[0], lpos[0]-lpos[1])
    rs = (rpos[0]-i, rpos[1]-rpos[0])
    c = ls[0]*rs[1] + ls[1]*rs[0]

    ans += c*(x+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
    data=[-1]*2+[n]*2
    now=p[i]
    for j in range(i-1,-1,-1):
        if p[j]>now:
            if data[1] == -1:
                data[1]=j
            else:
                data[0]=j
                break
    for j in range(i+1,n):
        if p[j]>now:
            if data[2] == n:
                data[2]=j
            else:
                data[3]=j
                break

    ans+=((data[1]-data[0])*(data[2]-i)+(data[3]-data[2])*(i-data[1]))*now  
print(ans)

Submission status: Time Limit Exceeded

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

Total = 0
for i in range(N-1):
    MaxValue    = max(P[i], P[i+1])
    SecondValue = min(P[i], P[i+1])
    Total = Total + SecondValue
    for j in range(i+2, N):
        v = P[j]
        if v > MaxValue:
            SecondValue = MaxValue
            MaxValue = v
        elif v > SecondValue:
            SecondValue = v
        Total = Total + SecondValue

print(Total)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9

class RmQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data_min = [INF] * (2*self.size-1)
        self.initialize(a)

    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data_min[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data_min[i] = min(self.data_min[i*2 + 1], self.data_min[i*2 + 2])

    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data_min[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data_min[k] = min(self.data_min[2*k+1], self.data_min[2*k+2])

    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data_min[R-1])
            if L & 1:
                s = min(s, self.data_min[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data_max = [-INF] * (2*self.size-1)
        self.initialize(a)

    # Initialize data_min
    def initialize(self, a):
        for i in range(self.n):
            self.data_max[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data_max[i] = max(self.data_max[i*2 + 1], self.data_max[i*2 + 2])

    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data_max[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data_max[k] = max(self.data_max[2*k+1], self.data_max[2*k+2])

    # Max value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = -INF 
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data_max[R-1])
            if L & 1:
                s = max(s, self.data_max[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n = int(input())
a = [int(item) for item in input().split()]
indexes = [0] * n
for i, item in enumerate(a):
    indexes[item - 1] = i
indexes.reverse()

a_min = [-1] * 2 + [INF] * n + [n] * 2
a_max = [-1] * 2 + [-INF] * n + [n] * 2
rMq = RMQ(a_max)
rmq = RmQ(a_min)
ans = 0
for i, idx in enumerate(indexes):
    num = n - i
    L1 = rMq.query(0, idx+2)
    L2 = rMq.query(0, L1+2)
    R1 = rmq.query(idx+2, n+4)
    R2 = rmq.query(R1+3, n+4)
    ans += (L1 - L2) * (R1 - idx) * num 
    ans += (idx - L1) * (R2 - R1) * num 
    rMq.update(idx+2, idx)
    rmq.update(idx+2, idx)
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[] for r in range( N)] for l in range(N-1)]


for l in range(N-1):

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

        if r == l+1:
            li = [P[l], P[r]]
            heapq.heapify(li)
            dp[l][r] = li
        elif P[r] >= dp[l][r-1][0]:
            li = dp[l][r-1][:]
            heapq.heappop(li)
            heapq.heappush(li, P[r])
            dp[l][r] = li
        else:
            li = dp[l][r-1][:]
            dp[l][r] = li


ans = 0
for l in range(N-1):
    for r in range(l+1, N):
        ans += dp[l][r][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
s = 0
pp = [sorted([p[i], p[i+1]]) for i in range(len(p)-1)]
while len(pp) > 0:
    s = s + sum(ppp[0] for ppp in pp)
    j = len(p) - len(pp) + 1
    pp = [sorted(pp[i] + [p[i+j]])[-2:] for i in range(len(pp)-1)]
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
s = 0
pp = [sorted([p[i], p[i+1]]) for i in range(len(p)-1)]
while len(pp) > 0:
    s = s + sum(ppp[0] for ppp in pp)
    j = len(p) - len(pp) + 1
    pp = [sorted([pp[i][1], max(pp[i][0], p[i+j])]) for i in range(len(pp)-1)]
print(s)

Submission status: Time Limit Exceeded

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

def sum_n(N):
    return N*(N+1)/2

Total = 0
for i in range(N-1):
    for j in range(i+1, N):
        sliced = P[i:j+1]
        sliced.sort()
        second = sliced[-2]
        Total = Total + second

print(Total)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P = list(map(int, input().split()))
t=0
for i in range(N):
  for j in range(i+1,N):
    P2=P[i:j+1]
    a=max(P2)
    b=0
    for k in P2:
      if k!=a:
        if k==a-1:
          b=k
          break
        elif k>b:
          b=k
          
    t+=b
print(t)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P = list(map(int, input().split()))
t=0
for i in range(N):
  for j in range(i+1,N):
    P2=P[i:j+1]
    P2.sort(reverse=True)
    t+=P2[1]
print(t)

Submission status: Time Limit Exceeded

Solution code:
def combi(l,x):
  res=0
  for i in range(l-1):
    for j in range(l):
      if i==j or i>j:
        continue
      res+=sorted(x[i:j+1])[-2]
  return res
l=int(input())
x=list(map(int,input().split()))
print(combi(l,x))

Submission status: Time Limit Exceeded

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

index = [0] * (n+1)

for i in range(n):
    index[p[i]] = i

poss = []
result = 0
for i in range(1, n+1)[::-1]:
    x = index[i]
    if len(poss) == 0:
        poss.append(x)
        continue
    dx = bisect.bisect_left(poss, x)
    # 左に１番目の数がある
    if dx > 0:
        lbl = 0
        if dx > 1:
            lbl = poss[dx-2]+1
        lbr = poss[dx-1]
        rbl = n-1
        if len(poss) != dx:
            rbl = poss[dx] -1
        result += (lbr-lbl+1) * (rbl-x+1) * i
    # 右に1番目の数がある
    if dx < len(poss):
        rbr = n-1
        if dx < len(poss) -1:
            rbr = poss[dx+1]-1
        rbl = poss[dx]
        lbr = 0
        if dx > 0:
            lbr = poss[dx-1] +1
        result += (rbr-rbl+1) * (x-lbr+1) * i
    poss.insert(dx, x)

print(result)

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()))

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		larger = len(largeind)-2
		smaller = 1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		# largeind.insert(larger,target)
		largeind[larger:larger]=[target]

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

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

	print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
p = np.array(list(map(int, input().split())))

score = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        score += np.sort(p[i : j + 1])[-2]
print(score)

Submission status: Time Limit Exceeded

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

score = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        score += sorted(p[i : j + 1])[-2]
print(score)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
input = sys.stdin.readline


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

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


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            v = self.__f(
                self.__table[2*pi+1], self.__table[2*pi+2])
            if v != self.__table[pi]:
                self.__table[pi] = v
            else:
                break
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]

        ans = self.__ie
        while stack:
            k, l, r = stack.pop()
            if a <= l and r <= b:
                ans = self.__f(ans, self.__table[k])
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans

def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i+1) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        lst.update(i, i)
        l = lst.query(0, i)
        ll = lst.query(0, l) if l != 0 else 0

        rst.update(i, i)
        r = rst.query(i+1, N+2)
        rr = rst.query(r+1, N+2) if r != N+1 else N + 1

        c = 0
        c += (l-ll) * (r-i)
        c += (i-l) * (rr-r)

        ans += c*p

    return ans


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


if __name__ == '__main__':
    main()

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 tuple(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


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            v = self.__f(
                self.__table[2*pi+1], self.__table[2*pi+2])
            if v != self.__table[pi]:
                self.__table[pi] = v
            else:
                break
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]

        ans = self.__ie
        while stack:
            k, l, r = stack.pop()
            if a <= l and r <= b:
                ans = self.__f(ans, self.__table[k])
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans


@mt
def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i+1) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        lst.update(i, i)
        l = lst.query(0, i)
        ll = lst.query(0, l) if l != 0 else 0

        rst.update(i, i)
        r = rst.query(i+1, N+2)
        rr = rst.query(r+1, N+2) if r != N+1 else N + 1

        c = 0
        c += (l-ll) * (r-i)
        c += (i-l) * (rr-r)

        ans += c*p

    return ans


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

    # N = 10**5
    # P = list(range(1, N+1))
    # random.shuffle(P)
    # print(N)
    # print(' '.join(map(str, P)))
    # # print(slv(N, P))


if __name__ == '__main__':
    main()

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


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi] = self.__f(self.__table[pi], self.__table[i])
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]

        ans = self.__ie
        while stack:
            k, l, r = stack.pop()
            cnd = self.__table[k]
            if a <= l and r <= b:
                ans = self.__f(ans, cnd)
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))

        return ans


    def print(self):
        print(self.__table)

@mt
def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        i += 1

        lst.update(i, i)
        l = lst.query(0, i)
        if l != 0:
            ll = lst.query(0, l)
        else:
            ll = 0
        rst.update(i, i)
        r = rst.query(i+1, N+2)
        if r != N+1:
            rr = rst.query(r+1, N+2)
        else:
            rr = N + 1
        c = 0
        c += (l-ll) * (r - i)
        c += (i-l) * (rr - r)

        ans += c*p

    return ans


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

    # N = 10**5
    # P = list(range(1, N+1))
    # random.shuffle(P)
    # print(slv(N, P))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(x) for x in input().split()]
L = [0] * (N + 2)
R = [N + 1] * (N + 2)
I = list(range(N + 1))
for i in range(N):
  I[P[i]] = i
ans = 0
ST = [0] * (N + 2)
def cnt(i):
  ret = 0
  while i:
    ret += ST[i]
    i -= i & (-i)
  return ret
def update(i):
  while i <= N + 1:
    ST[i] += 1
    i += i & (-i)
def ls(idx):
  b = cnt(idx)
  if b == 0:
    return 0
  s = 0
  t = idx
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) < b:
      s = m
    else:
      t = m
  return t
def rs(idx):
  b = cnt(idx)
  s = idx
  t = N + 1
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) > b:
      t = m
    else:
      s = m
  return t
for i in range(N, 0, -1):
  index = I[i]
  idx = index + 1
  L[idx] = ls(idx)
  R[idx] = rs(idx)
  L[R[idx]] = idx
  R[L[idx]] = idx
  update(idx)
  ans += i * ((idx - L[idx]) * (R[R[idx]] - R[idx]) + (L[idx] - L[L[idx]]) * (R[idx] - idx))
print(ans)

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


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi] = self.__f(self.__table[pi], self.__table[i])
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.__ie
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return self.__f(vl, vr)

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        i += 1

        lst.update(i, i)
        l = lst.query(0, i)
        if l != 0:
            ll = lst.query(0, l)
        else:
            ll = 0
        rst.update(i, i)
        r = rst.query(i+1, N+2)
        if r != N+1:
            rr = rst.query(r+1, N+2)
        else:
            rr = N + 1
        c = 0
        c += (l-ll) * (r - i)
        c += (i-l) * (rr - r)

        ans += c*p

    return ans


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

    # N = 10**5
    # P = list(range(1, N+1))
    # random.shuffle(P)
    # print(slv(N, P))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """
    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

# m~idxの間に出現済がない(この範囲の中で自分が最大値)かどうか
def calc1(m):
    cnt = lend - bit.sum(m-1)
    return cnt == 0

# m~idxの間に出現済が1つ以下(この範囲の中で自分が最大値か2番目)かどうか
def calc2(m):
    cnt = lend - bit.sum(m-1)
    return cnt <= 1

# idx~mの間に出現済がない(この範囲の中で自分が最大値)かどうか
def calc3(m):
    cnt = bit.sum(m) - rstart
    return cnt == 0

# idx~mの間に出現済が1つ以下(この範囲の中で自分が最大値か2番目)かどうか
def calc4(m):
    cnt = bit.sum(m) - rstart
    return cnt <= 1

N = INT()
A = LIST()
# aの昇順に処理できるようにindexで並べておく
idxs = [0] * (N+1)
for i, a in enumerate(A):
    idxs[a] = i + 1

bit = BIT(N+2)
# 先頭と末尾に番兵を仕込む
bit.add(0, 2)
bit.add(N+1, 2)
ans = [0] * (N+1)
# 大きいaから見ていく
for a in range(N, 0, -1):
    # a(N~1)が格納されているindex
    idx = idxs[a]
    # 左の終点と右の始点は各回固定なので先に取っておく
    lend = bit.sum(idx)
    rstart = bit.sum(idx-1)
    # 自分より小さいindexで2回目に自分より大きい値がある直前の場所
    p = bisearch_min(0, idx+1, calc2)
    # 自分より小さいindexで最初に自分より大きい値がある直前の場所
    q = bisearch_min(0, idx+1, calc1)
    # 自分より大きいindexで最初に自分より大きい値がある直前の場所
    r = bisearch_max(idx, N+1, calc3)
    # 自分より大きいindexで2回目に自分より大きい値がある直前の場所
    s = bisearch_max(idx, N+1, calc4)
    # aを使う回数 * a = (左に自分より大きい値がある時の通り数 + 右に自分より大きい値がある時の通り数) * a
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    # aを出現済とする
    bit.add(idx, 1)
# 全てのaについての合計
print(sum(ans))

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


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, monoido, identity_element):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__f = monoido
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi] = self.__f(self.__table[pi], self.__table[i])
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.__ie
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return self.__f(vl, vr)

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)

def slv(N, P):
    lst = SegmentTree(N+2, max, -1)
    rst = SegmentTree(N+2, min, sys.maxsize)
    P2 = [(p, i) for i, p in enumerate(P)]
    P2.sort(reverse=True)

    lst.update(0, 0)
    rst.update(0, 0)
    lst.update(N+1, N+1)
    rst.update(N+1, N+1)

    ans = 0
    for p, i in P2:
        i += 1

        lst.update(i, i)
        l = lst.query(0, i)
        if l != 0:
            ll = lst.query(0, l)
        else:
            ll = 0
        rst.update(i, i)
        r = rst.query(i+1, N+2)
        if r != N+1:
            rr = rst.query(r+1, N+2)
        else:
            rr = N + 1
        c = 0
        c += (l-ll) * (r - i)
        c += (i-l) * (rr - r)

        ans += c*p

    return ans



def slv3(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:
N = int(input())
P = [int(x) for x in input().split()]
L = [0] * (N + 2)
R = [N + 1] * (N + 2)
I = list(range(N + 1))
for i in range(N):
  I[P[i]] = i
cnt = 0
C = [0] * N
def ls(s, t):
  if s > t:
    return -1
  if s == t:
    return s if C[s] == 1 else -1
  m = (s + t) // 2
  return max(ls(s, m), ls(m + 1, t))
def rs(s, t):
  if s > t:
    return N
  if s == t:
    return s if C[s] == 1 else N
  m = (s + t) // 2
  return min(rs(s, m), rs(m + 1, t))
for i in range(N, 0, -1):
  index = I[i]
  idx = index + 1
  L[idx] = ls(0, index) + 1
  R[idx] = rs(idx, N - 1) + 1
  L[R[idx]] = idx
  R[L[idx]] = idx
  C[index] = 1
  cnt += i * ((idx - L[idx]) * (R[R[idx]] - R[idx]) + (L[idx] - L[L[idx]]) * (R[idx] - idx))
print(cnt)

Submission status: Time Limit Exceeded

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


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, sys.stdin.readline().rstrip().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)