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:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

# nodeをリストに変換したらクソ遅かった

import pprint

class BalancingTree:
    def __init__(self, n = 20):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def __str__(self):
        def debug_info(nd):
            return (nd.value - 1, nd.left.value - 1 if nd.left else None, nd.right.value - 1 if nd.right else None)

        def debug_node(nd):
            v = debug_info(nd) if nd.value else ()
            left = debug_node(nd.left) if nd.left else []
            right = debug_node(nd.right) if nd.right else []
            return [v, left, right]

        return pprint.PrettyPrinter(indent=4).pformat(debug_node(self.root))

    __repr__ = __str__

    def append(self, v):# v を追加（その時点で v はない前提）
        v += 1
        nd = self.root
        while True:
            # v がすでに存在する場合に何か処理が必要ならここに書く
            if v == nd.value:
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        return self.leftmost(nd.left) if nd.left else nd

    def rightmost(self, nd):
        return self.rightmost(nd.right) if nd.right else nd

    def find_l(self, v): # vより真に小さいやつの中での最大値（なければ-1）
        v += 1
        nd = self.root
        prev = nd.value if nd.value < v else 0
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): # vより真に大きいやつの中での最小値（なければRoot）
        v += 1
        nd = self.root
        prev = nd.value if nd.value > v else 0
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def max(self):
        return self.find_l((1<<self.N)-1)

    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除（なければ何もしない）
        v += 1
        if not nd:
            nd = self.root
        if not prev:
            prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    # v以下のものの中での最大値
    def lower_limit(self, v):
        upper = self.find_r(v)
        return self.find_l(upper)

    # v以上のものの中での最小値
    def lower_bound(self, v):
        lower = self.find_l(v)
        return self.find_r(lower)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None


def main():
    N = I()
    P = LI()

    tree = BalancingTree()
    stoi = [None] * (N + 1)

    for i, pi in enumerate(P):
        stoi[pi] = i

    tree.append(stoi[N])
    ans = 0

    for pi in range(1, N)[::-1]:
        i = stoi[pi]
        tree.append(i)
        l = tree.find_l(i)
        r = tree.find_r(i)
        k = (i + 1 if l == -1 else i - l)
        m = (N - i if r == tree.root.value - 1 else r - i)

        ll = tree.find_l(l)
        rr = tree.find_r(r)

        if l == -1:
            j = 0
        else:
            j = l + 1 if ll == -1 else l - ll
        if r == tree.root.value - 1:
            n = 0
        else:
            if rr == tree.root.value - 1:
                n = N - r
            else:
                n = rr - r

        ans += pi * (j * m + k * n)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*(N+1)
        self.b=1<<N.bit_length()-1
    def add(self,a,w):
        x=a
        while(x<=self.N):
            self.bit[x]+=w
            x+=x&-x
    def get(self,a):
        ret,x=0,a-1
        while(x>0):
            ret+=self.bit[x]
            x-=x&-x
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 
    def lowerbound(self,w):
        if w<=0:
            return 0
        x=0
        k=self.b
        while k>0:
            if x+k<=self.N and self.bit[x+k]<w:
                w-=self.bit[x+k]
                x+=k
            k//=2
        return x+1

N=int(input())
P=list(map(int,input().split()))
dic={}
bit=BIT(N)
for i in range(N):
    dic[P[i]]=i+1
dic[0]=0
dic[N+1]=N+1
ans=0
ng=[0,N+1]
for i in reversed(range(1,N+1)):
    bit.add(dic[i],1)
    c=bit.get(dic[i]+1)
    l1,l2=bit.lowerbound(c-1),bit.lowerbound(c-2)
    r1,r2=bit.lowerbound(c+1),bit.lowerbound(c+2)
    S=(l1-l2)*(r1-dic[i])+(r2-r1)*(dic[i]-l1)
    ans+=S*i
print(ans)

Submission status: Accepted

Solution code:
class SegmentTree():

    def __init__(self, iterable, func, e):
        self.func = func
        self.e = e
        ls = list(iterable)
        self.n = 1 << len(ls).bit_length()
        ls.extend( [self.e] * (self.n - len(ls)) )
        self.data = [self.e] * self.n + ls
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)


N = int(input())
Ps = list(map(lambda c: int(c) - 1, input().split()))

def max_tuple(t1, t2):
    if t1[0] < t2[0]:
        t1, t2 = t2, t1

    if t1[1] > t2[0]:
        return t1
    else:
        return (t1[0], t2[0])

max_two_elems = SegmentTree([(P, -1) for P in Ps], max_tuple, (-1, -1))

ans = 0
for i, P in enumerate(Ps):
    ok = 0
    ng = i + 1
    while ng - ok > 1:
        mid = (ng + ok) // 2
        largest, _ = max_two_elems.folded(i - mid, i + 1)
        if largest == P:
            ok = mid
        else:
            ng = mid
    l_width_1 = ng

    if l_width_1 == i + 1:
        l_width_2 = 0
    else:
        ok = 0
        ng = i - l_width_1 + 1
        while ng - ok > 1:
            mid = (ng + ok) // 2
            _, second_largest = max_two_elems.folded(i - l_width_1 - mid, i + 1)
            if second_largest <= P:
                ok = mid
            else:
                ng = mid
        l_width_2 = ng

    ok = 0
    ng = N - i
    while ng - ok > 1:
        mid = (ng + ok) // 2
        largest, _ = max_two_elems.folded(i, i + mid + 1)
        if largest == P:
            ok = mid
        else:
            ng = mid
    r_width_1 = ng

    if r_width_1 == N - i:
        r_width_2 = 0
    else:
        ok = 0
        ng = N - i - r_width_1
        while ng - ok > 1:
            mid = (ng + ok) // 2
            _, second_largest = max_two_elems.folded(i, i + r_width_1 + mid + 1)
            if second_largest <= P:
                ok = mid
            else:
                ng = mid
        r_width_2 = ng

    #print(P+1, l_width_2, l_width_1, r_width_1, r_width_2)
    ans += (l_width_2 * r_width_1 + l_width_1 * r_width_2) * (P + 1)
    
print(ans)

Submission status: Accepted

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

pos=[-1]*(N+1)

for i in range(N):
  pos[P[i]]=i
  
called=[-1,-1,pos[N],N,N]
ans=0
for i in range(N-1,0,-1):
  hoge=pos[i]
  r=bisect.bisect_left(called,hoge)
  R=called[r]
  RR=called[r+1]
  L=called[r-1]
  LL=called[r-2]
  ans+=i*((RR-R)*(hoge-L)+(L-LL)*(R-hoge))
  called.insert(r,hoge)
  #called=called[:r]+[hoge]+called[r:]
print(ans)

Submission status: Accepted

Solution code:

# 後でよく見る
# 構築は O(1)、挿入・削除・検索は O(log L)

class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def debug(self):
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):# v を追加（その時点で v はない前提）
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                # v がすでに存在する場合に何か処理が必要ならここに書く
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v): # vより真に小さいやつの中での最大値（なければ-1）
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): # vより真に大きいやつの中での最小値（なければRoot）
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    if prev == 2**17:
                        return N
                    else:
                        return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    if prev == 2**17:
                        return N
                    else:
                        return prev - 1

    @property
    def max(self):
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除（なければ何もしない）
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None


import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
P = LI()

A = []
for i in range(N):
    A.append((P[i],i))

A.sort(reverse=True)

BT = BalancingTree(17)

ans = 0
for i in range(N):
    x,y = A[i]
    BT.append(y)
    a = BT.find_l(y)
    b = BT.find_l(a)
    c = BT.find_r(y)
    d = BT.find_r(c)
    ans += ((a-b)*(c-y) + (d-c)*(y-a)) * x

print(ans)

Submission status: Accepted

Solution code:
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [-1] * i
            break
        else:
            i *= 2
    return tree

def initialization(tree, a):
    l = len(tree) // 2
    for i in range(l, l + len(a)):
        tree[i] = a[i - l]
    for i in range(l - 1, 0, -1):
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
    return

def update(tree, i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def find(tree, s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = -1
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans = max(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = max(ans, tree[t])
            t = (t - 1) // 2
    return ans

n = int(input())
p = list(map(int, input().split()))
q = [0] * n
tree = make_tree(n)
a = [[-1, -1] for _ in range(n)]
b = [[-1, -1] for _ in range(n)]
update(tree, p[0] - 1, 0)
for i in range(1, n):
    a[i][0] = find(tree, p[i], n - 1)
    if not a[i][0] == -1:
        update(tree, p[a[i][0]] - 1, -1)
        a[i][1] = find(tree, p[i], n - 1)
        update(tree, p[a[i][0]] - 1, a[i][0])
    update(tree, p[i] - 1, i)
#print(a)
initialization(tree, [-1] * n)
update(tree, p[-1] - 1, 0)
for i in range(1, n):
    j = n - i - 1
    b[j][0] = find(tree, p[j], n - 1)
    if not b[j][0] == -1:
        update(tree, p[n - b[j][0] - 1] - 1, -1)
        b[j][1] = find(tree, p[j], n - 1)
        update(tree, p[n - b[j][0] - 1] - 1, b[j][0])
    update(tree, p[j] - 1, i)
    if not b[j][0] == -1:
        b[j][0] = n - b[j][0] - 1
    if not b[j][1] == -1:
        b[j][1] = n - b[j][1] - 1
#print(b)
ans = 0
for i in range(n):
    if p[i] == n:
        continue
    if b[i][0] == -1:
        if not a[i][1] == -1:
            x = (n - i) * (a[i][0] - a[i][1])
        elif not a[i][0] == -1:
            x = (n - i) * (a[i][0] + 1)
    elif a[i][0] == -1:
        if not b[i][1] == -1:
            x = (i + 1) * (b[i][1] - b[i][0])
        elif not b[i][0] == -1:
            x = (i + 1) * (n - b[i][0])
    elif a[i][1] == b[i][1] == -1:
        x = (i - a[i][0]) * (n - b[i][0]) + (b[i][0] - i) * (a[i][0] + 1)
    elif b[i][1] == -1:
        x = (b[i][0] - i) * (a[i][0] - a[i][1]) + (i - a[i][0]) * (n - b[i][0])
    elif a[i][1] == -1:
        x = (i - a[i][0]) * (b[i][1] - b[i][0]) + (b[i][0] - i) * (a[i][0] + 1)
    else:
        x = (i - a[i][0]) * (b[i][1] - b[i][0]) + (b[i][0] - i) * (a[i][0] - a[i][1])
    ans += p[i] * x
    #print(ans)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic={}
for i in range(n):
    dic[p[i]]=i
# print(dic)

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    # [1,i]の足し算
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    # [i,j]の足し算
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i-1)

bi=BIT(n+1)
ans=0
for i in range(n)[::-1]:
    bi.add(dic[i+1]+1,i+1)
    # print(bi.el)
    lsum=bi.get(1,dic[i+1])
    l,r=-1,dic[i+1]
    while r-l>1:
        half=(r+l)//2
        if bi.get(1,half)>=lsum:
            r=half
        else:
            l=half
    l1=r
    l2=-1
    if r!=0:
        lsum=bi.get(1,r-1)
        l,r=-1,r-1
        while r-l>1:
            half=(r+l)//2
            if bi.get(1,half)>=lsum:
                r=half
            else:
                l=half
        l2=r
    # print(l1,l2)
    rsum=bi.get(dic[i+1]+2,n)
    l,r=dic[i+1]+2,n+2
    while r-l>1:
        half=(r+l)//2
        if bi.get(half,n)>=rsum:
            l=half
        else:
            r=half
    # print(rsum,l,r)
    r1=l
    r2=n+1
    if r!=n+1:
        rsum=bi.get(r1+1,n)
        l,r=r1+1,n+2
        while r-l>1:
            half=(r+l)//2
            if bi.get(half,n)>=rsum:
                l=half
            else:
                r=half
        r2=l
    # print(l2,l1)
    # print(r1,r2)
    # print(bi.el)
    if i==n-1:
        continue
    if l1+l2==-1:
        ans+=(dic[i+1]+1-l1)*(r2-r1)*(i+1)
    elif r1+r2==2*n+3:
        ans+=(l1-l2)*(r1-dic[i+1]-1)*(i+1)
    elif l2+4==r2:
        ans+=2*(i+1)
    else:
        ans+=((l1-l2)*(r1-dic[i+1]-1)+(dic[i+1]+1-l1)*(r2-r1))*(i+1)
    # print(l1-l2,r1-dic[i+1]-1,dic[i+1]+1-l1,r2-r1)
    # print(ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self._container = [0] * (n + 1)
        self.depth = n.bit_length()

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1


def main():
    n = int(readline())
    p = list(map(int, readline().split()))
    idx = dict()

    for i, x in enumerate(p):
        idx[x] = i + 1

    bt = BinaryIndexTree(n + 2)
    bt.add(n + 2, 2)
    bt.add(1, 2)
    ans = 0

    for num in range(n, 0, -1):
        i = idx[num]
        s = bt.sum(i + 1)
        l1 = bt.lower_bound(s)
        l2 = bt.lower_bound(s - 1)
        r1 = bt.lower_bound(s + 1)
        r2 = bt.lower_bound(s + 2)

        ans += num * (i + 1 - l1) * (r2 - r1)
        ans += num * (r1 - i - 1) * (l1 - l2)
        bt.add(i + 1, 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
#    n = 10**5
    p = [int(i) for i in ipt().split()]
#    p = [int(n-i) for i in range(n)]
    ip = [0]*(n+1)
    for i,pi in enumerate(p):
        ip[pi] = i
    ans = 0

    os = [-1,-1,n,n]
    for i in range(n,0,-1):
        pl = ip[i]
        j = bisect.bisect_left(os,pl)
        w,x,y,z = os[j-2],os[j-1],os[j],os[j+1]
        ans += i*((x-w)*(y-pl)+(pl-x)*(z-y))
        os.insert(j,pl)

    print(ans)


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.msb = 1 << (size.bit_length()-1)
    
    def add(self, i, w):
        i += 1
        while i < len(self.data):
            self.data[i] += w
            i += i & -i
    
    def get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            return self.get_sum(i.stop) if i.start is None else self.get_sum(i.stop) - self.get_sum(i.start)
        else:
            return 0 # fake value
    
    __setitem__ = add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right

def naive(P):
    def it():
        for i in range(len(P)-1):
            for j in range(i+1,len(P)):
                yield sorted(P[i:j+1])[-2]
    return sum(it())

def solve(P):

    def it():
        bit = BinaryIndexedTree(len(P))
        for cnt, (v,i) in enumerate(sorted(((v,i) for i,v in enumerate(P)), reverse=True)):
            bit[i] += 1
            c = bit.get_sum(i)
            low1 = -1 if c <= 0 else bit.bisect_left(c)
            low2 = -1 if c <= 1 else bit.bisect_left(c-1)
            up1 = len(P) if c > cnt-1 else bit.bisect_left(c+2)
            up2 = len(P) if c > cnt-2 else bit.bisect_left(c+3)
            yield v*((up1-i)*(low1-low2)+(i-low1)*(up2-up1))
    return sum(it())


if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    print(solve(P))

Submission status: Accepted

Solution code:

class BinaryIndexedTree:
    def __init__(self, size):
        size = 1 << (size-1).bit_length()
        self.data = [0] * (size+1)
        self.size = size
    
    def add(self, i, w):
        i += 1
        while i <= self.size:
            self.data[i] += w
            i += i & -i

    def sum(self, i):
        """
        [0,i)
        """
        result = 0
        while i > 0:
            result += self.data[i]
            i -= i & -i
        return result

    __getitem__ = sum

    def lower_bound(self, v):
        """
        return smallest i such that v < sum(data[:i])
        """

        s,pos = 0,0
        N = self.size
        k = N
        while k > 0:
            i = pos+k
            if i <= N:
                x = s+self.data[i]
                if x < v:
                    s = x
                    pos = i
            k >>= 1
        return pos


def naive(P):
    def it():
        for i in range(len(P)-1):
            for j in range(i+1,len(P)):
                yield sorted(P[i:j+1])[-2]
    return sum(it())

def solve(P):

    def it():
        bit = BinaryIndexedTree(len(P))
        for cnt, (v,i) in enumerate(sorted(((v,i) for i,v in enumerate(P)), reverse=True)):
            bit.add(i,1)
            c = bit.sum(i)
            
            low1 = -1 if c <= 0 else bit.lower_bound(c)
            low2 = -1 if c <= 1 else bit.lower_bound(c-1)
            up1 = len(P) if c > cnt-1 else bit.lower_bound(c+2)
            up2 = len(P) if c > cnt-2 else bit.lower_bound(c+3)
            yield v*((up1-i)*(low1-low2)+(i-low1)*(up2-up1))
    return sum(it())


if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    print(solve(P))

Submission status: Accepted

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

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -float("inf")
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.seg[i] = x
                

    def add(self, i, d):
        self.update(i, self.get(i)+d)

    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

n = int(input())
P = list(map(int, input().split()))
seg = RmaxQ(P)

def bs(i, p, right):
  if right:
    ok = i
    ng = n
    while ng - ok > 1:
      mid = (ok + ng) // 2
      if seg.query(i+1, mid+1) > p:
        ng = mid
      else:
        ok = mid
  else:
    ok = i
    ng = -1
    while ok - ng > 1:
      mid = (ok + ng) // 2
      if seg.query(mid, i) > p:
        ng = mid
      else:
        ok = mid
  return ng

ans = 0
for i, p in enumerate(P):
  r1 = bs(i, p, True)
  r2 = bs(r1, p, True)
  l1 = bs(i, p, False)
  l2 = bs(l1, p, False)
  ans += p * ((l1-l2)*(r1-i) + (i-l1)*(r2-r1))
print(ans)

Submission status: Accepted

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

'''
import random
N = 100000
P = list(range(1,N+1))
#random.shuffle(P)
'''

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i = i//2
            j = j//2
        return s

P2 = [[[p,i],[0,0]] for i,p in enumerate(P)]

max2 = lambda x,y : sorted(x+y,reverse=True)[:2]

seg = SegmentTree(P2,max2,[[0,0],[0,0]])

cand = [[0,N]]

ans = 0
visited = set([])
while cand:
    #print(cand)
    temp = []
    for l,r in cand:
        if r-l < 2:
            continue
        if (l,r) in visited:
            continue
        visited.add((l,r))
        (m1,i1), (m2,i2) = seg.get(l,r)
        #print(P[l:r],m1,m2)
        i1,i2 = (i1,i2) if i1 < i2 else (i2,i1)
        ans += m2 * (i1-l+1) * (r-i2)
        temp.append([l,i2])
        temp.append([i1+1,r])
    cand = temp

print(ans)