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: Accepted

Solution code:
# 区間和の計算と要素の更新が高速で必要
# l,rごとにやっていると日が暮れる→要素ごとに何回カウントされるかを考える
# 自分より左に大なもの1つ　かつ　右は0個
# 自分より右に大なもの1つ　かつ　左は0個
n = int(input())
P = list(map(int, input().split()))

# segment tree
# 1-index
# A[0]はSEG[num]に。A[n]はSEG[num+n]に
# SEG[i]の下はSEG[2i], SEG[2i+1]
# SEG[i]の上はSEG[i//2]
num = 2 ** (n.bit_length())
ele = 0
SEG = [ele] * (2 * num)


def func(a, b):
    return a + b


def update(idx, x):
    idx += num
    SEG[idx] += x
    idx //= 2
    while idx > 0:
        SEG[idx] = func(SEG[2 * idx], SEG[2 * idx + 1])
        idx //= 2


# [a,b)で定義
def query(a, b):
    a += num
    b += num - 1
    res = ele
    while b - a > 0:
        if a & 1 == 1:
            res = func(res, SEG[a])
            a += 1
        if b & 1 == 0:
            res = func(res, SEG[b])
            b -= 1
        a //= 2
        b //= 2
    if b == a:
        res = func(res, SEG[b])
    return res


def nibutan1(a):
    ok1 = a
    ng = n
    while ng - ok1 > 1:
        mid = (ng + ok1) // 2
        if query(a, mid + 1) == 0:
            ok1 = mid
        else:
            ng = mid
    if ok1 == n - 1:
        return n - 1, n - 1
    ok2 = 0
    ok2 += ok1
    ng = n
    while ng - ok2 > 1:
        mid = (ng + ok2) // 2
        if query(a, mid + 1) == 1:
            ok2 = mid
        else:
            ng = mid
    return ok1, ok2


def nibutan2(a):
    ok1 = a
    ng = -1
    while ok1 - ng > 1:
        mid = (ng + ok1) // 2
        if query(mid, a + 1) == 0:
            ok1 = mid
        else:
            ng = mid
    if ok1 == 0:
        return 0, 0
    ok2 = 0
    ok2 += ok1
    ng = -1
    while ok2 - ng > 1:
        mid = (ng + ok2) // 2
        if query(mid, a + 1) == 1:
            ok2 = mid
        else:
            ng = mid

    return ok1, ok2


A = [None] * n
for idx, v in enumerate(P):
    A[idx] = (v, idx)
A.sort(reverse=True)
ans = 0
for v, idx in A:
    migi1, migi2 = nibutan1(idx)
    hidari1, hidari2 = nibutan2(idx)
    # print("num", v, "idx", idx)
    # print(hidari1, hidari2, migi1, migi2)
    if migi1 == n - 1 and hidari1 == 0:
        pass
    elif migi1 == n - 1:
        ans += v * (migi1 - idx + 1) * (hidari1 - hidari2)
    elif hidari1 == 0:
        ans += v * (idx - hidari1 + 1) * (migi2 - migi1)
    else:
        ans += v * (migi1 - idx + 1) * (hidari1 - hidari2)
        ans += v * (idx - hidari1 + 1) * (migi2 - migi1)
    # print("ans", ans)
    update(idx, 1)
print(ans)

Submission status: Accepted

Solution code:
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.insert(j, i)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# second sum
# segment tree verify


class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] < x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] < x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


xx = int(input())
P = list(map(int, input().split()))
P = [10**18, 10**18]+P+[10**18, 10**18]  # sentinel
Q = []
for i, v in enumerate(P):
    Q.append((v, i))
Q.sort(reverse=True)
N = len(Q)
A = SegTree(N, max, 0)
ans = 0
for value, index in Q:
    A.update(index, value)
    if value < 10**18:
        l2 = A.find_max_index(0, index, value)
        l1 = A.find_max_index(0, l2, value)
        r1 = A.find_min_index(index+1, N, value)
        r2 = A.find_min_index(r1+1, N, value)

        if 1<l2:
            ans += value*((l2-l1)*(r1-index))

        if r1<N-2:
            ans += value*((r2-r1)*(index-l2))

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class OrderedSet:
    def __init__(self,a):
        self.c = {}
        self.r = {}
        self.a_sort = sorted(list(set(a)))
        for i,a in enumerate(self.a_sort):
            self.c[a] = i+1
            self.r[i+1] = a
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        self.num = [0]*self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self,x,k=1):
        index = self.c[x]
        self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    # xをk個削除する
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    # 格納しているxの数を返す
    def count(self,x):
        return self.num[self.c[x]-1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    # x以上の最小要素を返す
    def lower_bound(self,x):
        if x in self.c.keys():
            p = self.c[x]-1
        else:
            p = bisect_left(self.a_sort,x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    # x以下の最大要素を返す
    def upper_bound(self,x):
        if x in self.c.keys():
            p = self.c[x]
        else:
            p = bisect_right(self.a_sort,x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

N = I()
P = LI()

places = [0]*(N+1)
for i in range(N):
    places[P[i]] = i+1

s = OrderedSet(P)
ans = 0
for i in range(1,N+1)[::-1]:
    p = places[i]
    c = s.lower_bound(p)
    d = None if c is None else s.lower_bound(c+1)
    b = s.upper_bound(p)
    a = None if b is None else s.upper_bound(b-1)
    
    a = a if a is not None else 0
    d = d if d is not None else N+1

    if b is None:
        if c is not None:
            ans += i*p*(d-c)
    elif c is None:
        ans += i*(b-a)*(N-p+1)
    else:
        ans += i*((b-a)*(c-p)+(p-b)*(d-c))

    s.insert(p)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class OrderedSet:
    def __init__(self,a):
        self.c = {}
        #self.a_sort = sorted(list(set(a)))
        self.a_sort = a # 今回はソートがいらないので
        for i,a in enumerate(self.a_sort):
            self.c[a] = i + 1
        self.r = {v: k for k, v in self.c.items()}
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        self.num = [0]*self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self,x,k=1):
        index = self.c[x]
        self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    # xをk個削除する
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    # 格納しているxの数を返す
    def count(self,x):
        return self.num[self.c[x]-1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    # x以上の最小要素を返す
    def lower_bound(self,x):
        p = bisect_left(self.a_sort,x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    # x以下の最大要素を返す
    def upper_bound(self,x):
        p = bisect_right(self.a_sort,x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

N = I()
P = LI()

places = [0]*(N+1)
for i in range(N):
    places[P[i]] = i+1

s = OrderedSet([i for i in range(1,N+1)])
ans = 0
for i in range(1,N+1)[::-1]:
    p = places[i]
    c = s.lower_bound(p)
    d = None if c is None else s.lower_bound(c+1)
    b = s.upper_bound(p)
    a = None if b is None else s.upper_bound(b-1)
    
    a = a if a is not None else 0
    d = d if d is not None else N+1

    if b is None:
        if c is not None:
            ans += i*p*(d-c)
    elif c is None:
        ans += i*(b-a)*(N-p+1)
    else:
        ans += i*((b-a)*(c-p)+(p-b)*(d-c))

    s.insert(p)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class OrderedSet:
    def __init__(self,a):
        self.c = {}
        self.a_sort = sorted(list(set(a)))
        for i,a in enumerate(self.a_sort):
            self.c[a] = i + 1
        self.r = {v: k for k, v in self.c.items()}
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        self.num = [0]*self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self,x,k=1):
        index = self.c[x]
        self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    # xをk個削除する
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    # 格納しているxの数を返す
    def count(self,x):
        return self.num[self.c[x]-1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    # x以上の最小要素を返す
    def lower_bound(self,x):
        p = bisect_left(self.a_sort,x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    # x以下の最大要素を返す
    def upper_bound(self,x):
        p = bisect_right(self.a_sort,x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

N = I()
P = LI()

places = [0]*(N+1)
for i in range(N):
    places[P[i]] = i+1

s = OrderedSet(P)
ans = 0
for i in range(1,N+1)[::-1]:
    p = places[i]
    c = s.lower_bound(p)
    d = None if c is None else s.lower_bound(c+1)
    b = s.upper_bound(p)
    a = None if b is None else s.upper_bound(b-1)
    
    a = a if a is not None else 0
    d = d if d is not None else N+1

    if b is None:
        if c is not None:
            ans += i*p*(d-c)
    elif c is None:
        ans += i*(b-a)*(N-p+1)
    else:
        ans += i*((b-a)*(c-p)+(p-b)*(d-c))

    s.insert(p)

print(ans)

Submission status: Accepted

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

def main():
	N = int(input())
	p = list(map(int,input().split()))
	nl = [0]*N
	for i,num in enumerate(p):
		nl[num-1] = i+1
	nl.reverse()
	
	class BinaryIndexedTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = size
			self.default = default
			self.BIT = [default]*(self.size+1)
 
		# function(max, min, plus, minus, etc...)
		def BIT_segfunc(self, x, y):
			return x+y
 
		def BIT_query(self, idx):
			ret = self.default
			while idx > 0:
				ret = self.BIT_segfunc(ret, self.BIT[idx])
				idx -= idx&(-idx)
			return ret
 
		# update
		def BIT_update(self, idx, x):
			while idx <= self.size:
				self.BIT[idx] = self.BIT_segfunc(self.BIT[idx], x)
				idx += idx&(-idx)
			return
 
		def BIT_range(self, x, y):
			return self.BIT_query(y)-self.BIT_query(x)
 
		# BIT確認用
		def BIT_print(self):
			print(self.BIT)
			
		def BIT_search(self, x):
			i = 0
			s = 0
			step = 1<<(self.size.bit_length()-1)
			while step:
				if i+step <= self.size and s + self.BIT[i+step] < x:
					i += step
					s += self.BIT[i]
				step >>= 1
			return i+1
	
	BIT = BinaryIndexedTree(N, 0)
	ans = 0
	for i,num in enumerate(nl):
		l = BIT.BIT_query(num)
		BIT.BIT_update(num, 1)
		r = i-l
		a = BIT.BIT_search(l-1) if l >= 2 else 0
		b = BIT.BIT_search(l) if l >= 1 else 0
		d = BIT.BIT_search(l+2) if r >= 1 else N+1
		e = BIT.BIT_search(l+3) if r >= 2 else N+1
		ret = 0
		if b != 0:
			ret += (b-a)*(d-num)
		if d != 0:
			ret += (e-d)*(num-b)
		ans += ret*(N-i)
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    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

  #二分探索、x[未満or以下]のインデックス+1を返します
  def bs(self,x,side="l"):
    k = 1<<(self.bl-1)
    i = 0
    sm = 0
    flg = int(side!="l")
    while k:
      while i+k > self.size:
        k //= 2
      if sm+self.tree[i+k] < x+flg:
        sm += self.tree[i+k]
        i += k
      k //= 2
    return i+1

n = int(input())
a = list(map(int,input().split()))
da = {a[i]:i+1 for i in range(n)}
ans = 0
bit = Bit(n)
for i in range(n,0,-1):
  idx = da[i]
  x = bit.sum(idx)
  l2 = bit.bs(x-1,"l")
  l1 = bit.bs(x,"l")
  r1 = bit.bs(x+1,"l")
  r2 = bit.bs(x+2,"l")
  if i == n:
    bit.add(idx,1)
    continue
  if l1 == 1 or x == 1:
    l2 = 0
  if r1 == n+1:
    r2 = n+2
  if x == 0:
    ans += idx*(r2-r1)*i
  elif r1 == n+1:
    ans += (n-idx+1)*(l1-l2)*i
  else:
    if r1 < r2:
      ans += (r2-r1)*(idx-l1)*i
    if l2 < l1:
      ans += (l1-l2)*(r1-idx)*i
  bit.add(idx,1)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def get_nexts(p):
    d, e = [n for i in range(n)], [n for i in range(n)]
    stack1, stack2 = [], []
    for i in range(n):
        while stack2 and p[stack2[-1]] < p[i]:
            idx = stack2.pop()
            e[idx] = i

        to_append = []
        while stack1 and p[stack1[-1]] < p[i]:
            idx = stack1.pop()
            d[idx] = i
            to_append.append(idx)

        while to_append:
            stack2.append(to_append.pop())
        stack1.append(i)

    dist1, dist2 = [], []
    for i in range(n):
        dist1.append(d[i] - i)
        dist2.append(e[i] - d[i])
    return dist1, dist2

if __name__ == '__main__':
    n = int(stdin.readline().rstrip())
    p = list(map(int, stdin.readline().rstrip().split()))

    dist1, dist2 = get_nexts(p)
    dist3, dist4 = get_nexts(p[::-1])
    dist3, dist4 = dist3[::-1], dist4[::-1]

    ans = 0
    for i in range(n):
        ans += (dist1[i] * dist4[i] + dist2[i] * dist3[i]) * p[i]
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline().rstrip())
    p = list(map(int, stdin.readline().rstrip().split()))

    def get_nexts(p):
        d, e = [n for i in range(n)], [n for i in range(n)]
        stack1, stack2 = [], []
        for i in range(n):
            while stack2 and p[stack2[-1]] < p[i]:
                idx = stack2.pop()
                e[idx] = i

            to_append = []
            while stack1 and p[stack1[-1]] < p[i]:
                idx = stack1.pop()
                d[idx] = i
                to_append.append(idx)

            while to_append:
                stack2.append(to_append.pop())
            stack1.append(i)

        dist1, dist2 = [], []
        for i in range(n):
            dist1.append(d[i] - i)
            dist2.append(e[i] - d[i])
        return dist1, dist2

    dist1, dist2 = get_nexts(p)
    dist3, dist4 = get_nexts(p[::-1])
    dist3, dist4 = dist3[::-1], dist4[::-1]

    ans = 0
    for i in range(n):
        ans += (dist1[i] * dist4[i] + dist2[i] * dist3[i]) * p[i]
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline().rstrip())
    p = list(map(int, stdin.readline().rstrip().split()))

    def get_nexts(p):
        d, e = [n for i in range(n)], [n for i in range(n)]
        stack1, stack2 = [], []
        for i in range(n):
            while stack2 and p[stack2[-1]] < p[i]:
                idx = stack2.pop()
                e[idx] = i

            to_append = []
            while stack1 and p[stack1[-1]] < p[i]:
                idx = stack1.pop()
                d[idx] = i
                to_append.append(idx)

            while to_append:
                stack2.append(to_append.pop())
            stack1.append(i)

        dist1, dist2 = [], []
        for i in range(n):
            dist1.append(d[i] - i)
            dist2.append(e[i] - d[i])
        return dist1, dist2

    dist1, dist2 = get_nexts(p)
    dist3, dist4 = get_nexts(p[::-1])
    ans = 0
    for i in range(n):
        ans += (dist1[i] * dist4[n - 1 - i] + dist2[i] * dist3[n - 1 - i]) * p[i]
    print(ans)

Submission status: Accepted

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

def get_de(p):
    d, e = [n for i in range(n)], [n for i in range(n)]
    stack1 = []
    stack2 = []
    for i in range(n):
        while stack2 and p[stack2[-1]] < p[i]:
            idx = stack2.pop()
            e[idx] = i

        to_append = []
        while stack1 and p[stack1[-1]] < p[i]:
            idx = stack1.pop()
            d[idx] = i
            to_append.append(idx)

        while to_append:
            stack2.append(to_append.pop())
        stack1.append(i)

    dist1, dist2 = [], []
    for i in range(n):
        dist1.append(d[i] - i)
        dist2.append(e[i] - d[i])
    return dist1, dist2

dist1, dist2 = get_de(p)

dist3, dist4 = get_de(p[::-1])
dist3, dist4 = dist3[::-1], dist4[::-1]

ans = 0
for i in range(n):
    ans += (dist1[i] * dist4[i] + dist2[i] * dist3[i]) * p[i]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


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


def read_str_n():
    return readline().strip().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:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, P):
    pi = [(p, i) for i, p in enumerate(P)]
    pi.sort()
    p, i = pi.pop()
    lst = SegmentTree([-1]*N, max, -1)
    rst = SegmentTree([N]*N, min, N)
    lst.update(i, i)
    rst.update(i, i)

    ans = 0
    while pi:
        p, i = pi.pop()
        li = lst.query(0, i)
        lli = lst.query(0, li)
        ri = rst.query(i, N)
        rri = rst.query(ri+1, N)
        lst.update(i, i)
        rst.update(i, i)
        ln = (li-lli) * (ri-i)
        rn = (rri-ri) * (i-li)
        ans += (ln + rn) * p
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


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


def read_str_n():
    return readline().strip().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:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, P):
    pi = [(p, i) for i, p in enumerate(P)]
    pi.sort()
    p, i = pi.pop()
    lst = SegmentTree([-1]*N, max, -1)
    rst = SegmentTree([N]*N, min, N)
    lst.update(i, i)
    rst.update(i, i)

    ans = 0
    while pi:
        p, i = pi.pop()
        li = lst.query(0, i)
        lli = lst.query(0, li)
        ri = rst.query(i, N)
        rri = rst.query(ri+1, N)
        lst.update(i, i)
        rst.update(i, i)
        ln = (li-lli) * (ri-i)
        rn = (rri-ri) * (i-li)
        ans += ln * p
        ans += rn * p
    return ans


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


if __name__ == '__main__':
    main()