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:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    class BIT():
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
    
    N=int(input())
    P=list(map(int,input().split()))
    P2=[(P[i],i) for i in range(N)]
    P2.sort(reverse=True)
    b=BIT(N)
    
    def nibutan(i,num,ok,ng):
        b_sum_i=b.sum(i)
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(b_sum_i,i,num,mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(b_sum_i,i,num,mid):
        if i>mid:
            if b_sum_i-b.sum(mid-1) >= num:
                return True
        else:
            if b.sum(mid)-b_sum_i >= num:
                return True
        return False
    
    ans=0
    for p in P2:
        x=b.sum(p[1])
        y=b.sum(N-1)
        if x>=1 or y-x>=1:
            s=nibutan(p[1],1,-1,p[1])
            t=nibutan(p[1],2,-1,p[1])
            u=nibutan(p[1],1,N,p[1])
            v=nibutan(p[1],2,N,p[1])
            if x>=1:
                ans+=p[0]*(s-t)*(u-p[1]) if s>-1 else 0
            if y-x>=1:
                ans+=p[0]*(v-u)*(p[1]-s) if u<N else 0
        b.add(p[1],1)
    
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
sys.setrecursionlimit(100000)

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    P = [N+1,N+1] + ria() + [N+1,N+1]

    ord = []
    for i in range(2,N+2):
        ord.append((P[i], i))

    ord = sorted(ord) # P[i], i , P[i]順でソート

    # ..AsssBssCssDsssE.. のようになっている（Cが自分 A,B,D,E>C，s<C）
    # CからA,B,D,Eのインデクスを知りたいので，Cより小さい区間は連結にして置き，
    # スキップできるように各連結成分の両端に情報を乗せておく
    #  union-findで管理してもいいが，アクセスする場所と回数が限られているので配列で管理できる
    tot = 0
    l = [i for i in range(N + 4)]
    r = [i for i in range(N + 4)]
    used = [False] * (N + 4)
    for v, idx in ord:
        # 左右がusedならマージする
        used[idx] = True
        if used[idx - 1]:
            l[idx] = l[idx - 1]
        if used[idx + 1]:
            r[idx] = r[idx + 1]
        r[l[idx]] = r[idx]
        l[r[idx]] = l[idx]

        l0 = l[idx] - 1
        r0 = r[idx] + 1
        l1 = l0 - 1 if not used[l0 - 1] else (l[l0-1] - 1)
        r1 = r0 + 1 if not used[r0 + 1] else (r[r0+1] + 1)
        #print(l1,l0,idx,r0,r1)

        if l1 != 0:
            rseg = r0 - idx
            lseg = l0 - l1
            tot += lseg * rseg * v
        if r1 != N + 3:
            rseg = r1 - r0
            lseg = idx - l0
            tot += lseg * rseg * v

    print(tot)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

d_r = defaultdict(lambda:N+1)
h_r = []
d_r2 = defaultdict(lambda:N+1)
h_r2 = []
for i in range(N):
    p = P[i]
    while h_r2:
        q = heapq.heappop(h_r2)
        if q < p:
            d_r2[q] = p
        else:
            heapq.heappush(h_r2,q)
            break
    while h_r:
        q = heapq.heappop(h_r)
        if q < p:
            d_r[q] = p
            heapq.heappush(h_r2,q)
        else:
            heapq.heappush(h_r,q)
            break
    heapq.heappush(h_r,p)


d_l = defaultdict(lambda:0)
h_l = []
d_l2 = defaultdict(lambda:0)
h_l2 = []
for i in range(N-1,-1,-1):
    p = P[i]
    while h_l2:
        q = heapq.heappop(h_l2)
        if q < p:
            d_l2[q] = p
        else:
            heapq.heappush(h_l2,q)
            break
    while h_l:
        q = heapq.heappop(h_l)
        if q < p:
            d_l[q] = p
            heapq.heappush(h_l2,q)
        else:
            heapq.heappush(h_l,q)
            break
    heapq.heappush(h_l,p)

d = {}
for i in range(N):
    d[P[i]] = i
d[N+1] = N
d[0] = -1
ans = 0
for i in range(N):
    x = d[d_l2[P[i]]]
    y = d[d_l[P[i]]]
    z = d[d_r[P[i]]]
    w = d[d_r2[P[i]]]
    ans += P[i]*((y-x)*(z-i)+(w-z)*(i-y))
print(ans)

Submission status: Accepted

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

num_idx = [0]*(n+1)

# 自分のidxからみて右側で，自身の値より大きな値をもつ，一番近いidx
right_idx_over_current_pos = list(range(1, n+1)) + [n, n]
# 自分のidxからみて左側で，自身の値より大きな値をもつ，一番近いidx
left_idx_over_current_pos = list(range(-1, n-1)) + [-1, -1]

# 1から見ていくとすると，上記2つとも，自分のすぐ隣のidxがそのまま該当する

for idx, num in enumerate(P):
    num_idx[num] = idx

ans = 0
for num in range(1, n+1):  # 小さいほうから決める
    now = num_idx[num]
    r1 = right_idx_over_current_pos[now]
    r2 = right_idx_over_current_pos[r1]
    l1 = left_idx_over_current_pos[now]
    l2 = left_idx_over_current_pos[l1]

    r_pattern = (r2-r1) * (now-l1)
    l_pattern = (l1-l2) * (r1-now)

    right_idx_over_current_pos[l1] = r1  # l1にある値 > nowからr1までにある値 なので nowをスキップして r1までいける
    left_idx_over_current_pos[r1] = l1  # 上の左向きver
    ans += (r_pattern + l_pattern) * num

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=[int(j) for j in input().split()]
ans=0
ind=[0]*(n+1)
for i in range(n):
    ind[a[i]]=i+1
l=[0]+list(range(n+1))
r=list(range(1,n+2))+[n+1]
for i in range(1,n+1):
    l1=l[ind[i]]
    l0=l[l1]
    r0=r[ind[i]]
    r1=r[r0]
    ans+=((l1-l0)*(r0-ind[i])+(r1-r0)*(ind[i]-l1))*i
    l[r0]=l1
    r[l1]=r0

print(ans)

Submission status: Accepted

Solution code:
from random import random, sample


def bis_l(a, k):
  l = 0
  r = len(a)
  while l != r:
    m = (l + r) >> 1
    if a[m] < k:
      l = m + 1
    else:
      r = m
  return l


def bis_r(a, k):
  l = 0
  r = len(a)
  while l != r:
    m = (l + r) >> 1
    if a[m] <= k:
      l = m + 1
    else:
      r = m
  return l


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bis_l(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bis_l(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bis_l(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bis_l(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bis_l(top, key)
        block = self.bottom[top_i]
        block_i = bis_l(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bis_r(top, key)
        block = self.bottom[top_i]
        block_i = bis_r(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bis_r(top, key)
        block = self.bottom[top_i]
        block_i = bis_r(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bis_l(top, key)
        block = self.bottom[top_i]
        block_i = bis_l(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


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 = TwoLayerSet(1/100)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(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: Accepted

Solution code:

from bisect import bisect_left, bisect_right
from random import random, sample


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


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 = TwoLayerSet(1/100)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(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: Accepted

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

pos_list = [0] * n
# print(index_list) [0, 0, 0, 0] n = 4 のとき
for index, i in enumerate(p, 0):
    # print(index, i)
    pos_list[i - 1] = index
    # print(index_list)

left_next_index = list(range(-1, n-1)) + [-1, -1]
right_next_index = list(range(1, n+1)) + [n, n]

answer = 0
# print(left_next_index)    [-1, 0, 1, -1, -1]
# print(right_next_index)   [1, 2, 3, 3, 3]
for i in range(1, n):
    index = pos_list[i-1]
    l1 = left_next_index[index]
    l2 = left_next_index[l1]
    r1 = right_next_index[index]
    r2 = right_next_index[r1]
    # print(index, l1, l2, r1, r2, i)
    answer += i * ((index-l1) * (r2-r1) + (r1-index) * (l1-l2))

    left_next_index[r1] = l1
    right_next_index[l1] = r1

print(answer)

Submission status: Accepted

Solution code:
def main():
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[i for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            temp_list=[]
            temp=self.tree[index]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index]
            for i in temp_list:
                self.tree[i]=index
            return index
        
        #結合
        def unite_r(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1<r2:
                self.tree[r1]=r2
            else:
                self.tree[r2]=r1

        def unite_l(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1>r2:
                self.tree[r1]=r2
            else:
                self.tree[r2]=r1

        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
            
    n=int(input())
    a=list(map(int,input().split()))
    d=[0]*n
    for i,j in enumerate(a):
        d[j-1]=i+2
    vis=[False]*(n+4)
    u_r=unionfind(n+4)
    u_l=unionfind(n+4)
    ans=0
    for j,i in enumerate(d[:-1]):
        vis[i]=True
        if vis[i+1]==True:
            u_r.unite_r(i,i+1)
            u_l.unite_l(i,i+1)
            k1=u_r.root(i+1)+1
        else:
            k1=i+1
        if vis[k1+1]==True:
            cnt1=u_r.root(k1+1)+1
        else:
            cnt1=k1+1
        cnt1=min(cnt1,n+2)
        if vis[i-1]==True:
            u_r.unite_r(i,i-1)
            u_l.unite_l(i,i-1)
            k2=u_l.root(i-1)-1
        else:
            k2=i-1
        if vis[k2-1]==True:
            cnt2=u_l.root(k2-1)-1
        else:
            cnt2=k2-1
        cnt2=max(cnt2,1)
        ans+=((k2-cnt2)*(k1-i)+(cnt1-k1)*(i-k2))*(j+1)
    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[i for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            temp_list=[]
            temp=self.tree[index]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index]
            for i in temp_list:
                self.tree[i]=index
            return index
        
        #結合
        def unite_r(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1<r2:
                self.tree[r1]=r2
            else:
                self.tree[r2]=r1

        def unite_l(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1>r2:
                self.tree[r1]=r2
            else:
                self.tree[r2]=r1

        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
    
    n=int(input())
    a=list(map(int,input().split()))
    d=[0]*n
    for i,j in enumerate(a):
        d[j-1]=i+2
    vis=[False]*(n+4)
    u_r=unionfind(n+4)
    u_l=unionfind(n+4)
    ans=0
    #print(d)
    for j,i in enumerate(d[:-1]):
        vis[i]=True
        if vis[i+1]==True:
            u_r.unite_r(i,i+1)
            u_l.unite_l(i,i+1)
            k1=u_r.root(i+1)+1
        else:
            k1=i+1
        if vis[k1+1]==True:
            cnt1=u_r.root(k1+1)+1
        else:
            cnt1=k1+1
        cnt1=min(cnt1,n+2)
        if vis[i-1]==True:
            u_r.unite_r(i,i-1)
            u_l.unite_l(i,i-1)
            k2=u_l.root(i-1)-1
        else:
            k2=i-1
        if vis[k2-1]==True:
            cnt2=u_l.root(k2-1)-1
        else:
            cnt2=k2-1
        cnt2=max(cnt2,1)
        ans+=((k2-cnt2)*(k1-i)+(cnt1-k1)*(i-k2))*(j+1)
        #print(cnt2,k2,i-2,k1,cnt1)
    print(ans)
main()

Submission status: Accepted

Solution code:
N = int(input())
P = [None] + list(map(int, input().split()))

p_to_index = [None] * (N + 1)
for index, x in enumerate(P[1:], 1):
    p_to_index[x] = index


def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i & (-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i & (-i)
    return s

def BIT_search(x):
    i = 0
    s = 0
    step = 1 << (len(bin(N)[2:]) - 1)
    while step:
        if i + step <= N and s + tree[i + step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i + 1

tree = [0] * (N + 1)
ans = 0
for x in range(N, 0, -1):
    c = p_to_index[x]
    L = BIT_sum(c)
    R = N - x - L
    a = BIT_search(L - 1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L + 1) if R >= 1 else N + 1
    e = BIT_search(L + 2) if R >= 2 else N + 1
    BIT_add(c)
    tmp = 0
    if b != 0:
        tmp += (b - a) * (d - c)
    if d != 0:
        tmp += (e - d) * (c - b)
    ans += tmp * x

print (ans)

Submission status: Accepted

Solution code:
from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


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 = TwoLayerSet(1/50)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(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: Accepted

Solution code:
from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


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 = TwoLayerSet(1/1000)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(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: Accepted

Solution code:
from time import time
from statistics import median
from bisect import bisect_left, bisect_right
from random import random, sample


class TwoLayerSet:
    def __init__(self, p):
        self.top = []
        self.bottom = [[]]
        self.p = p

    def insert(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            return False
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            return False
        if random() < self.p:
            top.insert(top_i, key)
            bottom[top_i] = block[block_i:]
            bottom.insert(top_i, block[:block_i])
        else:
            block.insert(block_i, key)
        return True

    def erase(self, key):
        (top, bottom) = (self.top, self.bottom)
        top_i = bisect_left(top, key)
        if top_i != len(top) and key == top[top_i]:
            top.pop(top_i)
            bottom[top_i].extend(bottom.pop(top_i+1))
            return True
        block = bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block) and key == block[block_i]:
            block.pop(block_i)
            return True
        return False

    def less(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def less_equal(self, key):
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != 0:
            return block[block_i - 1]
        if top_i != 0:
            return top[top_i - 1]
        return None

    def greater(self, key):
        if key is None:
            return None
        top = self.top
        top_i = bisect_right(top, key)
        block = self.bottom[top_i]
        block_i = bisect_right(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None

    def greater_equal(self, key):
        top = self.top
        top_i = bisect_left(top, key)
        block = self.bottom[top_i]
        block_i = bisect_left(block, key)
        if block_i != len(block):
            return block[block_i]
        if top_i != len(top):
            return top[top_i]
        return None


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 = TwoLayerSet(1/100)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.greater(i)
        nexnex = t.greater(nex)
        pre = t.less(i)
        prepre = t.less(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: Accepted

Solution code:
def argsort(a):
    return list(map(lambda z: z[1], sorted(zip(a, range(len(a))))))

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

a = argsort(P)
left = [i for i in range(N)]
right = [i for i in range(N)]
result = 0
for i in range(1, N):
    k = a[i - 1]
    extend_left = k - 1 >= 0 and P[k - 1] < i
    extend_right = k + 1 < N and P[k + 1] < i
    if extend_left and extend_right:
        L = left[k - 1]
        R = right[k + 1]
    elif extend_left:
        L = left[k - 1]
        R = k
    elif extend_right:
        R = right[k + 1]
        L = k
    else:
        L = k
        R = k
    right[L] = R
    left[R] = L
    if L - 1 >= 0:
        if L - 2 >= 0 and P[L - 2] < i:
            LL = left[L - 2]
        else:
            LL = L - 1
        result += ((L - 1) - LL + 1) * (R - k + 1) * i;
    if R + 1 < N:
        if R + 2 < N and P[R + 2] < i:
            RR = right[R + 2]
        else:
            RR = R + 1
        result += (RR - (R + 1) + 1) * (k - L + 1) * i;
print(result)

Submission status: Accepted

Solution code:
n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)