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:
#incited from https://juppy.hatenablog.com/entry/2019/02/26/python_AVL%E6%9C%A8_%E9%85%8D%E5%88%97ver_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_
#AVL-Tree code by edamat
 
class Avltree:
    """
    AVL木
 
    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """
 
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
 
    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node  # node.key == keyの場合
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None
 
    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans
 
    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans
 
 
    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key
 
    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.key
 
 
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self  # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self, p, v):  # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else:
            p.right = v
    def insert(self, key):  # rootでのみ呼ばれる挿入
        if self.key is None:  # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self, key)
        else:  # key == self.key:
            pass  # do not overwrite
    def insertx(self, p, key):  # replaceを呼ぶために一つ上の親を持っているinsert
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    node = node.left
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    node = node.right
                    break
                else:
                    node = node.right
        while len(s) != 0:
            node, direct = s.pop()
            if len(s) != 0:
                par = s[-1][0]
            else:
                par = p
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(par, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(par, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(par, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(par, node.SingleLeftRotation())
                    break
 
    def to_s(self):
        return self.key
    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key

ans = 0
n = int(input())
p = list(enumerate((map(int,input().split()))))
p.sort(key = lambda x:x[1])
A = Avltree()
while p:
    index,x = p.pop()
    left2 = A.search_lower(index,-1)
    left1 = A.search_lower(left2,-1)
    right1 = A.search_higher(index,n)
    right2 = A.search_higher(right1,n)
    ans += ((left2-left1)*(right1-index)+(right2-right1)*(index-left2))*x
    A.insert(index)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter

n = int(readline())
ppp = list(map(int,readline().split()))

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):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        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

q = sorted(enumerate(ppp,1),key=itemgetter(1),reverse=True)
bit = Bit(n+4)
bit.add(1,1)
bit.add(2,1)
bit.add(n+3,1)
bit.add(n+4,1)

ans = 0
for i, p in q:
  f = bit.sum(i+2)
  LL = max(2,bit.lower_bound(f-1))
  LR = bit.lower_bound(f)
  RL = bit.lower_bound(f+1)
  RR = min(n+3,bit.lower_bound(f+2))
  ans += p*((i+2-LR)*(RR-RL)+(LR-LL)*(RL-i-2))
  bit.add(i+2,1)
  
print(ans)

Submission status: Accepted

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

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


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

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

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

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

print (ans)

Submission status: Accepted

Solution code:

class SegTree():
    def __init__(self, A):
        n_ = len(A)
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [float('inf') for _ in range(2 * self.n - 1)]
        for k, a in enumerate(A):
            self.update(k, a)
    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = float('inf')
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res


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

pii = []

for i, pi in enumerate(p):
    pii.append([pi, i])

pii.sort(reverse=True)

INF = 10 * n

st_r = SegTree([n] * (n+1))
st_l = SegTree([1] * (n+1))

ans = 0

for pi, i in pii:
    # print("###")
    # print(pi, i)
    # print(st_r.tree)
    if pi < n:
        l = -st_l.query(0, i)
        r = st_r.query(i+1, n)
        # print(l, r)
        if l != -1:
            l2 = l - 1
            if l > 0:
                l2 = -st_l.query(0, l)
            ans += (l - l2) * (r - i) * pi
        if r != n:
            r2 = r + 1
            if r < n - 1:
                r2 = st_r.query(r+1, n)
            ans += (i - l) * (r2 - r) * pi

    st_r.update(i, i)
    st_l.update(i, -i)

    
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter

n = int(readline())
ppp = list(map(int,readline().split()))

def BIT_add(i,x):
    while i <= n:
        tree[i] += x
        i += i&(-i)

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

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
      i = 0
      s = 0
      step = 1<<(n.bit_length()-1)
      while step:
          if i+step <= n and s + tree[i+step] < x:
              i += step
              s += tree[i]
          step >>= 1
      return i+1

q = sorted(enumerate(ppp,1),key=itemgetter(1),reverse=True)
tree = [0]*(n+1)

ans = 0
for i, p in q:
    L = BIT_sum(i) # 左にある既に書き込んだ数の個数
    BIT_add(i,1)
    R = n-p-L # 右にある既に書き込んだ数の個数
    LL = BIT_search(L-1) if L >= 2 else 0
    LR = BIT_search(L) if L >= 1 else 0
    RL = BIT_search(L+2) if R >= 1 else n+1
    RR = BIT_search(L+3) if R >= 2 else n+1
    ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
print(ans)

Submission status: Accepted

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

INF = 2**62-1


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


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


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


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


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


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

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

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

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


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += (l - ll) * (r-i)
        c += (rr - r) * (i-l)
        ans += c*p
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

INF = 2**62-1


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


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


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


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


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


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

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

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

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


def slv(N, P):

    lst = SegmentTree([0] * (N+1), max, 0)
    rst = SegmentTree([N+1] * (N+1), min, N+1)
    pi = [(p, i+1) for i, p in enumerate(P)]
    pi.sort(reverse=True)

    lst.update(pi[0][1], pi[0][1])
    rst.update(pi[0][1], pi[0][1])
    ans = 0
    for p, i in pi[1:]:
        l = lst.query(0, i+1)
        ll = lst.query(0, l)
        r = rst.query(i, N+1)
        rr = rst.query(r+1, N+1)

        lst.update(i, i)
        rst.update(i, i)
        c = 0
        c += max(0, (l - ll)) * (r-i)
        c += max(0, (rr - r)) * (i-l)
        ans += c*p
    return ans

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        a = self.func(self.table[log][i], self.table[log][j - (1<<log)])
        return a


def low(m, x):
    mi = 0
    ma = m - 1
    if ma < 0 or sp.get_section(0, m) <= x:
        return - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(mm, m) > x:
            mi = mm
        else:
            ma = mm - 1
    return mi


def high(m, x):
    mi = m
    ma = n - 1
    if m >= n or sp.get_section(m, n) <= x:
        return n
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(m, mm+1) > x:
            ma = mm
        else:
            mi = mm + 1
    return mi


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

sp = SparseTable(p)

ans = 0
for i in range(n):
    j = low(i, p[i])
    k = low(j, p[i])
    l = high(i, p[i])
    m = high(l+1, p[i])
    ans += p[i] * ((i-j) * (m-l) + (j-k) * (l-i))
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    class minseg():
        
        def __init__(self, arr):
            self.n = len(arr)
            self.ide_ele = arr[0]
            self.num =2**((self.n-1).bit_length())
            self.seg=[self.ide_ele]*2*self.num
            for i in range(self.n):
                self.seg[i+self.num-1]=arr[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 segfunc(self, x, y):
            return min(x, y)

            
        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                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 maxseg():
        
        def __init__(self, arr):
            self.n = len(arr)
            self.ide_ele = arr[0]
            self.num =2**((self.n-1).bit_length())
            self.seg=[self.ide_ele]*2*self.num
            for i in range(self.n):
                self.seg[i+self.num-1]=arr[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 segfunc(self, x, y):
            return max(x, y)

            
        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                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())
    a = list(map(int, input().split()))

    ind = {}
    for i in range(n):
        ind[a[i]] = i
    smax = maxseg([0]*(n+1))
    smin = minseg([n+1]*(n+1))

    res = 0
    for i in range(n):
        # 配列の1-indexed
        pos = ind[n-i] + 1

        l1 = smax.query(0, pos)
        l2 = smax.query(0, l1)
        r1 = smin.query(pos, n+2)
        r2 = smin.query(r1+1, n+2)
        res += ((l1-l2)*(r1-pos) + (r2-r1)*(pos-l1)) * (n-i)

        smin.update(pos, pos)
        smax.update(pos, pos)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    class minseg():
        
        def __init__(self, arr):
            self.n = len(arr)
            self.ide_ele = arr[0]
            self.num =2**((self.n-1).bit_length())
            self.seg=[self.ide_ele]*2*self.num
            for i in range(self.n):
                self.seg[i+self.num-1]=arr[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 segfunc(self, x, y):
            return min(x, y)

            
        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                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 maxseg():
        
        def __init__(self, arr):
            self.n = len(arr)
            self.ide_ele = arr[0]
            self.num =2**((self.n-1).bit_length())
            self.seg=[self.ide_ele]*2*self.num
            for i in range(self.n):
                self.seg[i+self.num-1]=arr[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 segfunc(self, x, y):
            return max(x, y)

            
        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                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())
    a = list(map(int, input().split()))

    ind = {}
    for i in range(n):
        ind[a[i]] = i
    smax = maxseg([0]*(n+2))
    smin = minseg([n+1]*(n+2))

    res = 0
    for i in range(n):
        # 配列の1-indexed
        pos = ind[n-i] + 1
        l1 = smax.query(0, pos)
        l2 = smax.query(0, l1)
        r1 = smin.query(pos, n+2)
        r2 = smin.query(r1+1, n+2)
        smin.update(pos, pos)
        smax.update(pos, pos)
        res += ((l1-l2)*(r1-pos) + (r2-r1)*(pos-l1)) * (n-i)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 区間ではなく各要素を独立に考える典型のやつ

# ある値について条件を満たすようにしたいとき
# その値より大きいものだけ探せば良い
# 具体的には自分より大きい値を1つだけ含むような区間が条件を満たす

# 愚直にやると各値について, その左右を近い方から順に見ていかなければならず間に合わない
# 自分より大きい値だけ知りたいので, 要素の大きい順に見ていくことで計算量が減る

# 普通にやったのが下のコードでAC+TLE(恐らく合ってる)

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

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

    # 1-indexed
    # f[i]:要素iのインデックス
    f = [0]*(n+1)
    for i in range(n):
        f[p[i]] = i+1

    # 各要素よりも大きい値のインデックスを参照するための配列
    l = [0] + [i for i in range(n+1)]
    r = [i + 1 for i in range(n+1)] + [n+1]

    res = 0

    for i in range(1,n+1):
        # x:要素iのインデックス
        x = f[i]
        
        # iは1から見ていくので, 選んだ時点でiより大きい数のインデックスが分かる
        l1,r1 = l[x],r[x]
        l2,r2 = l[l1],r[r1]

        res += ((l1-l2)*(r1-x) + (x-l1)*(r2-r1))*i

        # 要素iのインデックスをこれ以降参照することはないので消す
        l[r1],r[l1] = l1,r1

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *p = map(int, read().split())
ans = 0
l = list(range(n))
r = list(range(n))
memo = [-1] * (n + 1)
for i, pp in enumerate(p):
    memo[pp] = i
for i, idx in enumerate(memo[1:], 1):
    l1 = idx - 1
    r1 = idx + 1
    while l1 >= 0 and l1 != l[l1]:
        l1 = l[l1]
    while r1 < n and r1 != r[r1]:
        r1 = r[r1]
    l[idx] = l1
    r[idx] = r1
    if l1 != -1:
        l2 = l1 - 1
        while l2 >= 0 and l2 != l[l2]:
            l2 = l[l2]
        ans += (l1 - l2) * (r1 - idx) * i
    if r1 != n:
        r2 = r1 + 1
        while r2 < n and r2 != r[r2]:
            r2 = r[r2]
        ans += (r2 - r1) * (idx - l1) * i
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc140/submissions/7411285
# 写経

def main():
    N = int(input())
    *p, = map(int, input().split())

    xtoi = [-1] * (N + 1)
    for i, x in enumerate(p):
        xtoi[x] = i

    L = [-1] * (N + 2)
    R = [N] * (N + 2)
    for i in range(N):
        L[i] = i - 1
        R[i] = i + 1

    iter_inds = iter(xtoi)
    next(iter_inds)

    ans = 0
    for x, ind in enumerate(iter_inds, start=1):
        # l2, ..., l1, ..., x, ..., r1, ..., r2
        # (l2,r1) or (l1,r2)
        l1 = L[ind]
        l2 = L[l1]
        r1 = R[ind]
        r2 = R[r1]
        ans += x * ((l1 - l2) * (r1 - ind) + (r2 - r1) * (ind - l1))
        L[r1] = l1
        R[l1] = r1
    print(ans)


if __name__ == '__main__':
    main()