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
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    P=LI()
    #左右の自分より大きいものの位置を調べておく，2番目に近いやつまでまとめておけばよい
    #のだが，事前計算用の表を作るのにN^2かかるかも=>seg木で．
    

    #評価関数（という言い方であっている？）
    def segfunc1(x,y):
        #ここを書く！#########
        return max(x,y)

    #k番目の値をxに更新
    def update1(k,x):
        k += num-1
        seg1[k] = x
        while k:
            k = (k-1)//2
            seg1[k] = segfunc1(seg1[k*2+1],seg1[k*2+2])

            
    #[p,q)の区間に対するクエリへの応答
    def query1(p,q):
        if q<=p:
            return ide_ele1
        p += num-1
        q += num-2
        res=ide_ele1
        while q-p>1:
            if p&1 == 0:
                res = segfunc1(res,seg1[p])
            if q&1 == 1:
                res = segfunc1(res,seg1[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc1(res,seg1[p])
        else:
            res = segfunc1(segfunc1(res,seg1[p]),seg1[q])
        return res
    
    ######################################
    
    #評価関数（という言い方であっている？）
    def segfunc2(x,y):
        #ここを書く！#########
        return min(x,y)

    #k番目の値をxに更新
    def update2(k,x):
        k += num-1
        seg2[k] = x
        while k:
            k = (k-1)//2
            seg2[k] = segfunc2(seg2[k*2+1],seg2[k*2+2])

            
    #[p,q)の区間に対するクエリへの応答
    def query2(p,q):
        if q<=p:
            return ide_ele2
        p += num-1
        q += num-2
        res=ide_ele2
        while q-p>1:
            if p&1 == 0:
                res = segfunc2(res,seg2[p])
            if q&1 == 1:
                res = segfunc2(res,seg2[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc2(res,seg2[p])
        else:
            res = segfunc2(segfunc2(res,seg2[p]),seg2[q])
        return res

    #####単位元######
    ide_ele1 = 0
    ide_ele2 = 10**10



    #num:N+2以上の最小の2のべき乗
    num =2**(N+1).bit_length()
    seg1=[ide_ele1]*2*num#最大値を求める
    seg2=[ide_ele2]*2*num#最小値を求める
    
    #大きい順にみていく，みたらセグ木を更新しておく，座標=xならseg[x]=xにしておく，自分以下の最大値を見れば，左側にあるかつ自分より大きい一番近いやつの座標が取れる．
    #最小値ももてば左側でもできる．2番目に近いのも，直近から次の範囲で見ればok
    
    px=[[0,0]for _ in range(N)]
    for x in range(N):
        px[x]=[P[x],x+1]
    px.sort(reverse=True)
    
    a=[0]*(N+2)#左二番目
    b=[0]*(N+2)#左一番目
    c=[0]*(N+2)#右一番目
    d=[0]*(N+2)#右二番目

    
    update2(N+1,N+1)#他のinfよりは小さい
    
    for i in range(N):
        p=px[i][0]
        x=px[i][1]
        update1(x,x)
        update2(x,x)
        b[x]=query1(0,x)
        c[x]=query2(x+1,N+2)
        if b[x]<=0:
            a[x]=0
        else:
            a[x]=query1(0,b[x])
            
        if c[x]>=N+1:
            d[x]=N+1
        else:
            d[x]=query2(c[x]+1,N+2)
            
    ans=0
    
    
    for i in range(1,N+1):
        if b[i]!=0:
            cnt=(b[i]-a[i])*(c[i]-i)
            ans+=cnt*P[i-1]
        if c[i]!=(N+1):
            cnt=(i-b[i])*(d[i]-c[i])
            ans+=cnt*P[i-1]
            
    print(ans)
            
    
    

main()

Submission status: Accepted

Solution code:
n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))
left  = {i: i - 1 for i in range(n)}
right = {i: i + 1 for i in range(n)}
left[-1] = -1
right[n] = n

ret = 0
for p, i in pi:
    ret += p * (left[i] - left[left[i]]) * (right[i] - i)
    ret += p * (i - left[i]) * (right[right[i]] - right[i])
    l, r = left[i], right[i]
    right[l] = r
    left[r] = l
print(ret)

Submission status: Accepted

Solution code:
n=int(input())
p=list(map(int,input().split()))
ind=[0]*n
for i in range(n):ind[p[i]-1]=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(n):
  ans+=(r[r[ind[i]]]-r[ind[i]])*(ind[i]-l[ind[i]])*(i+1)
  ans+=(l[ind[i]]-l[l[ind[i]]])*(r[ind[i]]-ind[i])*(i+1)
  l[r[ind[i]]],r[l[ind[i]]]=l[ind[i]],r[ind[i]]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = [int(i) for i in input().split(" ")]

# 各数字が何番目に入っているかを保存する
pos = [0] * (N + 1)
for i in range(N):
    pos[P[i]] = i + 1

l = [0]+[i for i in range(N + 1)]
r = [i + 1 for i in range(N + 1)] + [N + 1]

# 1から順番に見ていく
ans = 0
for i in range(1, N + 1):
    idx = pos[i]
    l1, r1 = l[idx], r[idx]
    l2, r2 = l[l1], r[r1]
    ans += i * ((l1 - l2) * (r1 - idx) + (idx - l1) * (r2 - r1))
    l[r1], r[l1] = l1, r1
print(ans)

Submission status: Accepted

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

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

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

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

N = int(input())
P = list(map(int, input().split()))
idx = [-1] * (N+1)
for i, p in enumerate(P):
    idx[p] = i + 1
bit = BIT(N+1)
bit.add(0, 1)
ans = 0

def bin_search(target):
    lb, ub = -1, N+1
    while ub - lb > 1:
        m = (lb + ub) // 2
        if bit.sum(m) < target:
            lb = m
        else:
            ub = m
    return ub

for p in range(1, N+1)[::-1]:
    c = idx[p]
    s = bit.sum(c)
    a = bin_search(s-1)
    b = bin_search(s)
    d = bin_search(s+1)
    e = bin_search(s+2)
    ans += p * ((b-a) * (d-c) + (c-b) * (e-d))
    bit.add(c, 1)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class BinaryIndexedTree:
    # 1-indexed
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def sum(self, i):
        res = 0
        while i:
            res += self.data[i]
            i -= i & -i
        return res
    
    def bisect_left(self, w):
        if w <= 0:
            return 0
        i = 0
        k = 1 << (self.n.bit_length() - 1)
        while 0 < k:
            if i + k <= self.n and self.data[i + k] < w:
                w -= self.data[i + k]
                i += k
            k >>= 1
        return i + 1


def solve():
    N = int(rl())
    P = list(map(int, rl().split()))
    
    p_to_idx = [0] * (N + 1)
    for i, x in enumerate(P):
        p_to_idx[x] = i + 1
    
    bit = BinaryIndexedTree(N)
    ans = 0
    for pi in range(N, 0, -1):
        idx = p_to_idx[pi]
        left = bit.sum(idx)
        bit.add(idx, 1)
        right = N - pi - left
        l0 = bit.bisect_left(left - 1) if 2 <= left else 0
        l1 = bit.bisect_left(left) if 1 <= left else 0
        r0 = bit.bisect_left(left + 2) if 1 <= right else N + 1
        r1 = bit.bisect_left(left + 3) if 2 <= right else N + 1
        cnt = 0
        if l1 != 0:
            cnt += (l1 - l0) * (r0 - idx)
        if r0 != 0:
            cnt += (r1 - r0) * (idx - l1)
        ans += pi * cnt
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
p = list(map(int,input().split()))
p_ind = [ (p[i], i+1) for i in range(n) ]
p_ind.sort(reverse=True)

# 平方分割します。
max_n = 10**5
div_n = int(max_n**(1/2))+1
a = [[] for _ in range(div_n)]
a[0] = [0,0]
a[(n+1)//div_n].append(n+1)
a[(n+1)//div_n].append(n+1)
a_count = [0] * (div_n)
a_count[0] += 2
a_count[(n+1)//div_n] += 2

import bisect
ans = 0
for tmp in p_ind:
    val, i = tmp
    group = i//div_n
    j = bisect.bisect(a[group],i)
    #left
    if(j>1):
        left1 = a[group][j-1]
        left2 = a[group][j-2]
    elif(j==1):
        left1 = a[group][j-1]
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        left2 = a[lg][-1]
    else:
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        if(a_count[lg]>=2):
            left1 = a[lg][-1]
            left2 = a[lg][-2]
        else:
            left1 = a[lg][-1]
            while(True):
                lg -=1
                if(a_count[lg]>0):
                    break
            left2 = a[lg][-1]
    #right
    if(a_count[group]>=j+2):
        right1 = a[group][j]
        right2 = a[group][j+1]
    elif(a_count[group]>=j+1):
        right1 = a[group][j]
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        right2 = a[rg][0]
    else:
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        if(a_count[rg]>=2):
            right1 = a[rg][0]
            right2 = a[rg][1]
        else:
            right1 = a[rg][0]
            while(True):
                rg += 1
                if(a_count[rg]>0):
                    break
            right2 = a[rg][0]

    ans += ((right2 - right1)* (i - left1) + (right1 - i)* (left1 - left2)) * val
    a[group].insert(j,i)
    a_count[group] += 1

print(ans)

Submission status: Accepted

Solution code:
# Treap
#平衡二分木　乱数を用いてできるだけ平衡を保つらしい　
#priorityには乱数を入れること
# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c

root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    # [<left>, <right>, <key>, <priority>, <count>]
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def find(val):
    global root
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def search1(val):
    global root
    x = root
    ans=-1
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            ans=max(ans,x[2])
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

def search2(val):
    global root,N
    x=root
    ans=N
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            ans=min(ans,x[2])
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

import random

N=int(input())
P=list(map(int,input().split()))
dic={key:-1 for key in range(1,N+1)}
for i in range(0,N):
    dic[P[i]]=i

answer=0
for i in range(0,N):
    k=N-i
    l1=search1(dic[k])
    l2=search1(l1-1)
    r1=search2(dic[k])
    r2=search2(r1+1)
    answer+=k*(dic[k]-l1)*(r2-r1)+k*(l1-l2)*(r1-dic[k])
    insert(dic[k],random.randint(1,100000))

print(answer)

Submission status: Accepted

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

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
p=list(map(int,input().split()))
l=[0]+[i for i in range(n+1)]#l_i...p_iよりも大きいもので、左側かつp_iに一番近い要素のindex
r=[i+1 for i in range(n+1)]+[n+1]#r_i...l_iの右側ver
d=[0]*(n+1)
for i in range(n):d[p[i]]=i+1
ans=0
for i in range(1,n+1):
  ans+=((r[r[d[i]]]-r[d[i]])*(d[i]-l[d[i]])+(r[d[i]]-d[i])*(l[d[i]]-l[l[d[i]]]))*i#l_iでで一番近い、l_(l_i)で二番目に近い(indexの差分取ってアレコレ計算)
  l[r[d[i]]],r[l[d[i]]]=l[d[i]],r[d[i]]#右側(左側)にある一番近いものを、自分を飛び越えて左側(右側)にくっつける(大小比較はしなくても良くて、どうせ後でまた更新される)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
n=int(input())
p=list(map(int,input().split()))
idx=[0]*(n+1)

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

right_idx=list(range(1,n+1))+[n,n]
left_idx =list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=idx[p]
    r1=right_idx[x]
    r2=right_idx[r1]
    l1=left_idx[x]
    l2=left_idx[l1]

    ans+=p*( (x-l1)*(r2-r1) + (l1-l2)*(r1-x)  )
    right_idx[l1]=r1
    left_idx[r1]=l1
print(ans)

Submission status: Accepted

Solution code:
import bisect


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

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

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]
                
    def dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")
            
            
def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: -p[i])
    t = SqrtSet()
    t.insert(-10)
    t.insert(n+10)
    ans = 0
    for i in range(n):
        if i==0:
            t.insert(idx[i])
            continue
        ri = t.search_higher(idx[i])
        pri = t.search_higher(ri)
        if pri==None:
            pri=n
            ri=n
        if pri==n+10:
            pri=n
        le = t.search_lower(idx[i])
        ple=t.search_lower(le)
        if ple==None:
            if le==-10:
                le=-1
                ple=-1
        if ple==-10:
            ple=-1
        #print(ple,le,idx[i],ri,pri)
        ans+=(n-i)*((le-ple)*(ri-idx[i])+(pri-ri)*(idx[i]-le))
        #print(n-i,ans)
        t.insert(idx[i])
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def search(self, key, leastValue, largestValue):
        t = self.root
        lb, hb = leastValue, largestValue
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 
 
    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    L, R = dict(), dict()
    for i, p in enumerate(P): pindex[p - 1] = i 
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])

    if N == 10 ** 5:
        for i in range(N-2, 0, -1):
            pid = pindex[i]
            left, right = T.lower_bound(pid, -1), T.upper_bound(pid, N)
            if left == -1: l2 = -1
            else: l2 = T.lower_bound(left, -1)
            if right == N: r2 = N
            else: r2 = T.upper_bound(right, N)
            Ans += (i + 1) * ((pid - left) * (r2 - right) + (right - pid) * (left - l2))
            T.insert(pid)
        Ans += (2 if 0 < pindex[0] < N - 1 else 1)

    else:
        L[pindex[N-1]] = -1
        R[pindex[N-1]] = N
        L[-1] = L[N] = -1
        R[-1] = R[N] = N    
        for i in reversed(range(N-1)):
            pid = pindex[i]
            L[pid], R[pid] = l, r = T.search(pid, -1, N)
            Ans += (i + 1) * ((pid - l) * (R[r] - r) + (r - pid) * (l - L[l]))
            T.insert(pid)
            R[l] = L[r] = pid

    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# Cumulative Sum Bisect


class SegTree():
    def __init__(self, N, e=0, operator_func=lambda x,y:x+y):
        self.e = e

        self.N = N
        bitlen = (N).bit_length()
        self.size = 2**(bitlen if N&(N-1) else bitlen-1)
        self.node = [self.e] * (2*self.size)
        self.op = operator_func

    def set_list(self, l):
        for i,j in enumerate(l):
            self.node[i+self.size-1] = j
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

    def bisect_left(self, x):
        if x > self.node[0]:
            return self.N
        p, ans = 0, 0
        node_size = 2 * self.size - 1
        x -= 1

        while p < node_size:
            ans = p - (self.size - 1)
            p1, p2 = 2 * p + 1, 2 * p + 2

            if p1 < node_size and self.node[p1] <= x:
                x -= self.node[p1]
                p = p2
            else:
                p = p1
        
        return ans+1


if __name__ == "__main__":
    # ABC140-E sample
    N = int(input())
    l = [(j, i) for i, j in enumerate(map(int, input().split()))]
    l.sort(key=lambda x:-x[0])
    tree = SegTree(N)
 
    ans = 0
 
    for n, (value, idx) in enumerate(l, start=1):
        v = tree.get(0, idx + 1)
        a = tree.bisect_left(v - 1) if v > 1 else 0
        b = tree.bisect_left(v - 0) if v else 0
        c = tree.bisect_left(v + 1) if n-v>1 else N+1
        d = tree.bisect_left(v + 2) if n-v>2 else N+1
 
        tree.update(idx, 1)
        idx += 1
        ans += ((b-a)*(c-idx)+(d-c)*(idx-b)) * value
 
    print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.dat = [0]*n

    def add(self, k, a):
        while k < self.n:
            self.dat[k] += a
            k |= k+1
 
    def sum(self, k):
        s = 0
        while k >= 0:
            s += self.dat[k]
            k = (k & (k+1)) - 1
        return s

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

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

bit = BIT(N)
ans = 0
for i in range(N, 0, -1):
    bit.add(pos[i], 1)
    s = bit.sum(pos[i])
    bound = []
    for s2 in [s-2, s-1, s+1, s+2]:
        if s2 <= 0:
            bound.append(-1)
            continue
        
        ok, ng = N, -1
        while ok-ng>1:
            mid = (ok+ng)>>1
            if bit.sum(mid) >= s2:
                ok = mid
            else:
                ng = mid
        bound.append(ok)
    res = (bound[1]-bound[0])*(bound[2]-pos[i]) + (pos[i]-bound[1])*(bound[3]-bound[2])
    ans += i*res

print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    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 lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth + 1)[::-1]:
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


N = int(input())
l = [(j, i) for i, j in enumerate(map(int, input().split()))]
l.sort(key=lambda x:-x[0])
tree = BIT(N)
m = [0]*N
ans = 0

for value, idx in l:
    v = tree.sum(idx + 1)

    a = tree.lower_bound(v - 1)[0] if v>1 else 0
    b = tree.lower_bound(v - 0)[0] if v else 0
    c = tree.lower_bound(v + 1)[0] 
    d = tree.lower_bound(v + 2)[0]

    tree.add(idx + 1, 1)
    idx += 1
    ans += ((b-a)*(c-idx)+(d-c)*(idx-b)) * value

print(ans)

Submission status: Accepted

Solution code:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        # n = 2 ** (len(A) - 1).bit_length()
        n = 2 ** (A - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        # for i in range(len(A)):
        #     self.__node[i + n] = A[i]
        # for i in range(n - 1, 0, -1):
        #     self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree(N, max, -1)
    minSeg = SegmentTree(N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()

Submission status: Accepted

Solution code:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        # n = 2 ** (len(A) - 1).bit_length()
        n = A
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        # for i in range(len(A)):
        #     self.__node[i + n] = A[i]
        # for i in range(n - 1, 0, -1):
        #     self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree(N, max, -1)
    minSeg = SegmentTree(N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()