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
#ABC140 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
p = LI()
f = [0]*(n+1)
for i in range(n):
    f[p[i]] = i+1

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

#1-indexed
for i in range(1,n+1):
    #x:= p.index(i)
    x = f[i]
    
    #l1:= xの左にある1つ目のiよりも大きい数のindex
    #r1:= xの右にある1つ目のiよりも大きい数のindex
    l1,r1 = l[x],r[x]
    #l2:= xの左にある2つ目のiよりも大きい数のindex(= l1の左にある1つ目のiよりも大きい数のindex)
    #r2:= xの右にある2つ目のiよりも大きい数のindex(= r1の右にある1つ目のiよりも大きい数のindex)
    l2,r2 = l[l1],r[r1]
    #ans:= ans + (l1を含みr2を含まない場合 + r1を含みl2を含まない場合) * i
    ans += ((l1-l2)*(r1-x) + (x-l1)*(r2-r1))*i
    #r1の左にある1つ目のiよりも大きい数のindex = l1
    #l1の右にある1つ目のiよりも大きい数のindex = r1
    l[r1],r[l1] = l1,r1
print(ans)

Submission status: Accepted

Solution code:
class Node:
  def __init__(self, v):
    self.v = v
    self.p = None
    self.n = None
  
  def delete(self):
    if self.p:
      self.p.n = self.n
    if self.n:
      self.n.p = self.p

N = int(input())
pp = list(map(int, input().split()))
nn = dict()
prev = None
for i, p in enumerate(pp):
  n = Node(i)
  if prev:
    prev.n = n
    n.p = prev
  nn[p] = n
  prev = n
s = 0
for x in range(1, N):
  c = nn[x]
  ci = c.v
  pi = c.p.v if c.p else -1
  ni = c.n.v if c.n else N
  if c.p:
    ppi = c.p.p.v if c.p.p else -1
    s += x * (pi - ppi) * (ni - ci)
  if c.n:
    nni = c.n.n.v if c.n.n else N
    s += x * (ci - pi) * (nni - ni)
  c.delete()
print(s)

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(int, input().split()))
 
index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index
 
left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))
 
    left_next_Index[r1] = l1
    right_next_Index[l1] = r1
 
print (ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import array

n = int(input())
p = []

for i, x in enumerate(map(int, input().split())):
    p.append([x, i])

p.sort(reverse=True)

s = array.array('i', [-1, -1, p[0][1], n, n])

#print(p)

ans = 0
i = 2
for a, x in p[1:]:
    t = bisect_left(s, x)
    ans += a * ((x - s[t-1]) * (s[t+1] - s[t]) + (s[t] - x) * (s[t-1] - s[t-2]))
    #print(t, s)
    s.insert(t, x)
    i += 1


print(ans)

Submission status: Accepted

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

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

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

for j in range(1,N+1):
    f = ind[j]

    l1 = l[f]
    l2 = l[l1]
    r1 = r[f]
    r2 = r[r1]
    ans += ((l1-l2)*(r1-f) + (f-l1)*(r2-r1))*j

    l[r1] = l1
    r[l1] = r1

print(ans)

Submission status: Accepted

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

index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index

left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
# print (left_next_Index)
# print (right_next_Index)
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))

    left_next_Index[r1] = l1
    right_next_Index[l1] = r1

print (ans)

Submission status: Accepted

Solution code:

class SegTree:

    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n = int(input())
xs = list(map(int, input().split()))
x2i = {}
for i, x in enumerate(xs):
    x2i[x] = i
ss1 = SegTree([n] * n, n, n, min)
ss2 = SegTree([-1] * n, n, -1, max)

r = 0
for x in range(n):
    x = n - x
    rmi2 = ss1.query(x2i[x]+1, n)
    if rmi2 != n:
        ss1.update(rmi2, n)
    rmi = ss1.query(x2i[x]+1, n)
    if rmi2 != n:
        ss1.update(rmi2, rmi2)

    lmi = ss2.query(0, x2i[x])
    if lmi != -1:
        ss2.update(lmi, -1)
    lmi2 = ss2.query(0, x2i[x])
    if lmi != -1:
        ss2.update(lmi, lmi)
    a,b,c,d =(x2i[x] - lmi), (lmi - lmi2), (rmi - rmi2), (rmi2 - x2i[x])
    r += (a*c + b*d) * x
#    print(x, r)
#    print(rmi, rmi2, lmi, lmi2)
    ss1.update(x2i[x], x2i[x])
    ss2.update(x2i[x], x2i[x])
print(r)

Submission status: Accepted

Solution code:
n = int(input())
xs = list(map(int, input().split()))
x2i = {}
for i, x in enumerate(xs):
    x2i[x] = i+1
ll = [0] * (n+2)
rr = [n+1] * (n+2)

def find_l(l, r, default):
    m, m2 = 0, 0
    mi=mi2=default
    for i in range(r-l):
        i = i + l
        if ll[i] > m:
            mi, m = i, ll[i]
    for i in range(r-l):
        i = i + l
        if i == mi:
            continue
        if ll[i] > m2:
            mi2, m2 = i, ll[i]
    return max(mi, mi2), min(mi, mi2)

def find_r(l, r, default):
    m, m2 = n+1, n+1
    mi=mi2=default
    for i in range(r-l):
        i = i + l
        if rr[i] < m:
            mi, m = i, rr[i]
    for i in range(r-l):
        i = i + l
        if i == mi:
            continue
        if rr[i] < m2:
            mi2, m2 = i, rr[i]
    return max(mi, mi2), min(mi, mi2)

class ss_min:

    def __init__(self, init_val, n, ide_ele):
        self.segfunc = min
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
class ss_max:

    def __init__(self, init_val, n, ide_ele):
        self.segfunc = max
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

ssmm = ss_min(rr, n+2, n+1)
ssmm2 = ss_max(ll, n+2, 0)

r = 0
for x in range(n):
    x = n - x
#    lmi, lmi2 = find_l(0, x2i[x], 0)

    rmi2 = ssmm.query(x2i[x]+1, n+1)
    ssmm.update(rmi2, n+1)
    rmi = ssmm.query(x2i[x]+1, n+1)
    ssmm.update(rmi2, rmi2)

    lmi = ssmm2.query(0, x2i[x])
    ssmm2.update(lmi, 0)
    lmi2 = ssmm2.query(0, x2i[x])
    ssmm2.update(lmi, lmi)

    a,b,c,d =(x2i[x] - lmi), (lmi - lmi2), (rmi - rmi2), (rmi2 - x2i[x])
    r += (a*c + b*d) * x
#    print(x, r)
#    print(rmi, rmi2, lmi, lmi2)
    ll[x2i[x]] = x2i[x]
    ssmm.update(x2i[x], x2i[x])
    ssmm2.update(x2i[x], x2i[x])
print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12(i, j):
        if j - i <= 0:
            return (0, 0)

        segi = 0
        top = []

        while True:
            if j - i <= 0:
                break

            seg = segt[segi]

            if j - i == 1:
                top.extend(seg[i])
                break

            if i % 2 == 1:
                top.extend(seg[i])
                i += 1
            if j % 2 == 1:
                top.extend(seg[j - 1])
                j -= 1

            i //= 2
            j //= 2
            segi += 1

        top.sort()
        return top[-1], top[-2]

    cache = dict()

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if (i, j) in cache:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or (c, d) in cache):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[(c, d)]
                                    for c, d in want]
                cache[(i, j)] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[(c, d)]
                            for c, d in want]
        cache[(i, j)] = left + right - mid + sc

    return cache[(0, N)]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12(i, j):
        if j - i <= 0:
            return (0, 0)

        segi = 0
        top = []

        while True:
            if j - i <= 0:
                break

            seg = segt[segi]

            if j - i == 1:
                top.extend(seg[i])
                break

            if i % 2 == 1:
                top.extend(seg[i])
                i += 1
            if j % 2 == 1:
                top.extend(seg[j - 1])
                j -= 1

            i //= 2
            j //= 2
            segi += 1

        top.sort()
        return top[-1], top[-2]

    cache = [dict() for _ in range(N)]

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if j in cache[i]:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or d in cache[c]):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[c][d]
                                    for c, d in want]
                cache[i][j] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[c][d]
                            for c, d in want]
        cache[i][j] = left + right - mid + sc

    return cache[0][N]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        lo = -1
        hi = self.N
        while lo < hi:
            mid = (lo+hi)//2
            if self.query(mid) < x:
                lo = mid + 1
            else:
                hi = mid
        return lo


def main():
    N = int(input())
    P = list(map(int, input().split()))
    idx = [0] * N
    bit = BinaryIndexedTree(N)
    for i in range(N):
        idx[P[i]-1] = i
    ans = 0
    for i in range(N)[::-1]:
        bit.add(idx[i], 1)
        x = bit.query(idx[i])
        l = bit.search(x-1)
        ll = bit.search(x-2)
        r = bit.search(x+1)
        rr = bit.search(x+2)
        tmp = (idx[i]-l) * (rr-r) + (r-idx[i]) * (l-ll)
        ans += (i+1) * tmp
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
P = [None] + [int(x) for x in input().split()]
id_list = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    id_list[x] = i

# 左隣にあるインデックスを取得できるようにしておく
# Binary Iindex Treeを使うことで、区間[L,R]内での和をとれば[L,R]内のデータ件数を数えられる
class BIT:
    def __init__(self, n):
        # 要素数を与えてインスタンス化
        self.size = n
        self.tree = [0] * (n + 1) # index must be 1-origin

    def add(self, i, x=1):
        # add x(>= 1) to a_i
        while i <= self.size:
            self.tree[i] += x
            i += i&(-i) # i&(-i) = BITでのi番目の区間の長さ

    def sum(self, i):
        # sum of a_1, a_2, ... , a_i
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i) # i&(-i) = BITでのi番目の区間の長さ
        return s

    def search(self, x):
        # 二分探索。a_1 + a_2 + ... + a_i >= xなる最小のインデックスi(>= 1)を返す
        i = 0
        s = 0
        step = 1<<(N.bit_length()-1) # the largest 2^k (= step) <= N
        while step:
            if i+step <= N and s + self.tree[i+step] < x:
                i += step
                s += self.tree[i]
            step >>= 1
        return i+1


def main():
    bit = BIT(N)
    ans = 0
    for x in range(N,0,-1):
        idx = id_list[x]
        L = bit.sum(idx) # 左にある既に書き込んだ数の個数
        bit.add(idx)
        R = N-x-L # 右にある既に書き込んだ数の個数
        ll = bit.search(L-1) if L >= 2 else 0
        l = bit.search(L) if L >= 1 else 0
        r = bit.search(L+2) if R >= 1 else N+1
        rr = bit.search(L+3) if R >= 2 else N+1
        coef = 0
        if l != 0:
            # [b,c]を含むようにする。(a,b) と(c,d)が自由
            coef += (l - ll) * (r - idx)
        if r != 0:
            # [c,d]を含むようにする。
            coef += (rr - r) * (idx - l)
        ans += x * coef
    print(ans)

main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

class Bit:
    def __init__(self,n):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        
    def __str__(self):
        return str(self.arr)
        
    def add(self,i,x):
        k=0
        while i<=self.size:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1

        
class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)

n=I()
a=LI()
p=[i+1 for i,j in sorted(enumerate(a),key=lambda x:x[1])]
bt=Bit0(n+2)
bt.add(0,1)
bt.add(n+1,1)
ans=0
for i in range(n-1,-1,-1):
    c=bt.sum(p[i])
    w,x,y,z=[bt.l_bound(c-1+i) for i in range(4)]
    c=p[i]
    bt.add(p[i],1)
    d=(i+1)*((x-w)*(y-c)+(c-x)*(z-y))
    ans+=d
print(ans)

Submission status: Accepted

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

pos = {}
for i, p in enumerate(P):
    pos[p] = i+1

foll = [i+1 for i in range(N+1)]+[N+1]
prev = [0]+[i for i in range(N+1)]

ans = 0
for i in range(1, N+1):
    curr = pos[i]
    r = foll[curr]
    rr = foll[r]
    l = prev[curr]
    ll = prev[l]
    ans += (l-ll)*(r-curr)*i
    ans += (rr-r)*(curr-l)*i

    foll[l] = foll[curr]
    prev[r] = prev[curr]
    # print(*foll)
    # print(*prev)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
P=list(map(int,input().split()))
I=[0]*N
for i,p in enumerate(P):
    I[N-p]=i
class BIT:
    def __init__(self,size):
        self.N=size
        self.v=[0]*(self.N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.v[i]+=x
            i+=i&-i
    def sum(self,a,b=0):
        if a>b:
            a,b=b,a
        if a>0:
            r=self.sum(b)-self.sum(a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.v[i]
                i-=i&-i
        return r
    def right(self,x):
        a,b=x+1,self.N
        while a+1<b:
            t=(a+b)//2
            if self.sum(a,t)>0:
                b=t
            else:
                a=t
        return a 
    def left(self,x):
        a,b=0,x
        while a+1<b:
            t=(a+b)//2
            if self.sum(t,b)>0:
                a=t
            else:
                b=t
        return a
b=BIT(2**17)
b.add(0,N+1)
b.add(1,N+1)
b.add(N+2,N+1)
b.add(N+3,N+1)
a=0
p=N
for i in I:
    l=b.left(i+2)
    ll=b.left(l)
    r=b.right(i+2)
    rr=b.right(r)
    if 1<l and r<N+2:
        a+=((l-ll)*(r-i-2)+(rr-r)*(i+2-l))*p
    elif 1<l:
        a+=(l-ll)*(N-i)*p
    elif r<N+2:
        a+=(rr-r)*(i+1)*p
    b.add(i+2,p)
    p-=1
print(a)

Submission status: Accepted

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

class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + 1
    s.T[k - 1] = max(s.T[k - 1], v)
    k += k & -k
    while k <= s.N:
      s.T[k - 1] = max(s.T[k - 1], v)
      k += k & -k
  def getV(s, x):
    if x <= 0:
      return 0
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans = max(ans, s.T[x - 1])
      x -= x & -x
    return ans

class segMin:
  inf = N + 1
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    if l > r:
      return s.inf
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

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

TMa = BIT(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  #print(ans)
  t = D[i]
  ma = TMa.getV(t)
  ma2 = TMa.getV(ma)

  mi = TMi.getV(t, N + 1)
  mi2 = TMi.getV(mi + 1, N + 1)
  #print(ma2, ma, t, mi, mi2, ans)
  TMa.update(t, t)
  TMi.update(t, t)
  ans += (mi - t) * (ma - ma2) * i
  ans += (mi2 - mi) * (t - ma) * i

print(ans)

Submission status: Accepted

Solution code:
# 平方分割に勝てない～～～～～～～～～～～～～～
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (add, pop) データ構造: https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (init, add, remove, search_higher_equal) Exclusive OR Queries: https://atcoder.jp/contests/cpsco2019-s1/submissions/7488225
    # 検証3 (add, search_higher, search_lower) Second Sum: https://atcoder.jp/contests/abc140/submissions/7485479
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= (y & 0x7ffff) << 13
                y ^= y >> 17
                y ^= (y & 0x7ffffff) << 5
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        # xorshift
        y = self.rand_y
        y ^= (y & 0x7ffff) << 13
        y ^= y >> 17
        y ^= (y & 0x7ffffff) << 5
        self.rand_y = y

        if y % self.square == 0:
            layer1, layer0 = self.layer1, self.layer0
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(self.layer1, x)
            insort_right(self.layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del self.layer1[idx1]
            self.layer0[idx1] += self.layer0.pop(idx1+1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        idx1 = bisect_right(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return self.layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

    def print(self):
        print(self.layer1)
        print(self.layer0)


def main():
    # 参考: https://atcoder.jp/contests/abc140/submissions/7477790
    inf = float("inf")
    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])
    ssl = SquareSkipList()
    ssl.add(-1)
    ssl.add(n)
    ans = 0
    for i in idx:
        nex = ssl.search_higher(i)
        nexnex = ssl.search_higher(nex)
        pre = ssl.search_lower(i)
        prepre = ssl.search_lower(pre)
        if prepre != inf:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != inf:
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

dpl = [[] for _ in range(N)]
dpr = [[] for _ in range(N)]
q = []
for i in range(N-1, -1, -1) :
    L = []
    while len(q) > 0 and q[0][0] < P[i] :
        v, j = heappop(q)
        if len(dpl[j]) == 0 :
            L.append([v, j])
        dpl[j].append(i)
    for v, j in L :
        heappush(q, [v, j])
    heappush(q, [P[i], i])

q = []
for i in range(N) :
    L = []
    while len(q) > 0 and q[0][0] < P[i] :
        v, j = heappop(q)
        if len(dpr[j]) == 0 :
            L.append([v, j])
        dpr[j].append(i)
    for v, j in L :
        heappush(q, [v, j])
    heappush(q, [P[i], i])

for i in range(N) :
    for _ in range(2-len(dpl[i])) :
        dpl[i].append(-1)
    for _ in range(2-len(dpr[i])) :
        dpr[i].append(N)
    dpl[i].sort()
    dpr[i].sort()

ret = 0
for i in range(N) :
    ret += (dpl[i][1]-dpl[i][0]) * (dpr[i][0]-i) * P[i]
    ret += (i-dpl[i][1]) * (dpr[i][1] - dpr[i][0]) * P[i]

print(ret)