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:
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (データ構造): https://atcoder.jp/contests/arc033/submissions/7480578
    # 検証2 (Exclusive OR Queries): https://atcoder.jp/contests/cpsco2019-s1/submissions/7479914
    # 検証3 (Second Sum): https://atcoder.jp/contests/abc140/submissions/7480312
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        if self.rand_depth():
            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 で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

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

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

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        #res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて res で埋まっている場合
            return layer1[idx1-1]
        else:
            return layer0_idx1[idx0-1]
        # if res != x:  # res > x
        #     if layer0_idx1:
        #         idx0 = bisect_left(layer0_idx1, x)
        #         if idx0 != 0:
        #             return layer0_idx1[idx0-1]
        #     return layer1[idx1-1]  # layer0_idx1 が空の場合とすべて x 以上の場合
        # else:
        #     idx0 = bisect_left(layer0_idx1, x)
        #     if idx0 == 0:  # layer0_idx1 が空の場合とすべて res で埋まっている場合
        #         return layer1[idx1-1]
        #     else:
        #         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
    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 != float("inf"):
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != float("inf"):
            ans += p[i] * (i - pre) * (nexnex - nex)
        ssl.add(i)
    print(ans)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
import random
import bisect
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class BIT:
    '''
    BinaryIndexedTreeのクラス。0-indexed に統一してあるので0からn-1までの配列と思って使える。

    Parameters
    ----------
        n (Union(int, list)): int なら使う BIT のサイズ。list ならそのlistで BIT を初期化する
    '''
    def __init__(self, x, d=0):
        if isinstance(x, int):
            self.size = x
            self.tree = [d for _ in range(self.size + 1)]
        elif isinstance(x, list):
            self.size = len(x)
            self.tree = [d for _ in range(self.size + 1)]
            self.build(x)
        else:
            raise TypeError

    def build(self, arr):
        """
        初期化されたあとのBITをリストの値に設定する

        Parameters
        ----------
            arr (list): 元のlsit

        Raises
        ------
            TypeError: 入力はlistでないといけないことに注意してください。
        """
        if not isinstance(arr, list):
            raise TypeError
        for num, x in enumerate(arr):
            self.add(num, x)

    def sum(self, i):
        '''[0,i) の和'''
        if i < 0:
            return 0
        s = self.tree[0]
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
        return s

    def add(self, i, a):
        i += 1
        '''i番目の要素にaを足す'''
        if(i == 0):
            return
        while (i <= self.size):
            self.tree[i] += a
            i += (i & -i)

    def lower_bound(self, w):
        '''[0,i]の和 >= w をみたす最小の index
        Examples
        ----------
        >>> bit = BIT([1,0,0,1,0,1,0])
        >>> bit.lower_bound(1)
        0
        >>> bit.lower_bound(2)
        3
        >>> bit.lower_bound(3)
        5
        '''
        if w <= 0:
            return -1
        x = 0
        k = 1 << (self.size.bit_length() - 1)
        while k:
            if x + k <= self.size and self.tree[x + k] < w:
                w -= self.tree[x + k]
                x += k
            k >>= 1
        return x

    def getKthNum(self, w):
        '''k番目(k = 0, 1, ...)に小さい数を返す'''
        w += 1
        return self.lower_bound(w)

    def upper_bound(self, w):
        w += 0.00000000001
        return self.lower_bound(w)

    def query(self, l, r):
        '''[l, r)の和を求める
        >>> bit = BIT([1,2,3,4,5])
        >>> bit.query(1,4)
        9
        >>> bit.query(0,2)
        3
        '''
        return self.sum(r) - self.sum(l)

    # 出力関係（デバッグのみに用いる）
    def __getitem__(self, item):
        if not isinstance(item, int):
            _tmp = item.indices(self.size + 1)
            return [self.sum(i + 1) - self.sum(i) for i in range(_tmp[0], _tmp[1], _tmp[2])]
        else:
            return self.sum(item + 1) - self.sum(item)
    def __str__(self):
        return str(self[0:self.size])
# END CUT HERE

class sqrtDecomposition():
    def __init__(self, N):
        self.BASE = 1000
        self.size = 0
        self.a = [[] for i in range(ceil(N / self.BASE))]
        self.b = BIT(ceil(N / self.BASE))

    def insert(self, i):
        self.size += 1
        idx = bisect.bisect_left(self.a[i // self.BASE], i)
        self.a[i // self.BASE].insert(idx, i)
        self.b.add(i // self.BASE, 1)
        return (i // self.BASE, idx)

    def _next(self, key, idx1, idx2):
        if key >= self.size:
            return (None, None)
        if len(self.a[idx1]) - 1 == idx2:
            idx = self.b.lower_bound(key + 1)
            return (idx, 0)
        else:
            return (idx1, idx2 + 1)

    def _prev(self, key, idx1, idx2):
        if key <= 0:
            return (None, None)
        if idx2 == 0:
            idx = self.b.lower_bound(key)
            return (idx, len(self.a[idx]) - 1)
        else:
            return (idx1, idx2 - 1)

    def get(self, left, right):
        left += 1
        right += 1
        idx1, idx2 = None, None
        for key in range(left, right):
            # debug(key, self.size)
            if key <= 0 or key > self.size:
                yield (None, None)
                continue
            if not idx1:
                idx1 = self.b.lower_bound(key)
                idx2 = key - self.b.sum(idx1) - 1
            else:
                idx1, idx2 = self._next(key - 1, idx1, idx2)
            yield (idx1, idx2)

def main():
    # N = 10**5
    # P = [i for i in range(N)]
    # random.shuffle(P)
    N = ii()
    P = lmi()
    t = sqrtDecomposition(N)
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    # debug(L)
    ans = 0
    for num, i in enumerate(L):
        c = t.insert(i)
        idx = t.b.sum(c[0]) + c[1]
        l = [-1] * 4
        l[1] = t._prev(idx, *c)
        l[0] = t._prev(idx - 1, *l[1])
        l[2] = t._next(idx + 1, *c)
        l[3] = t._next(idx + 2, *l[2])
        # debug(idx, l[0], l[1], l[2], l[3])
        for j in range(4):
            if l[j][0] is not None:
                l[j] = t.a[l[j][0]][l[j][1]]
            else:
                if j >= 2:
                    l[j] = N
                else:
                    l[j] = -1

        # debug(l[0], l[1], l[2], l[3])
        ans += (abs(i - l[1]) * abs(l[3] - l[2]) + abs(l[1] - l[0]) * abs(l[2] - i)) * (N - num)
    print(ans)
    return


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
        import cProfile
        cProfile.run('for i in range(100): main()', sort=1)
    else:
        main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
import random
import bisect
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class BIT:
    '''
    BinaryIndexedTreeのクラス。0-indexed に統一してあるので0からn-1までの配列と思って使える。

    Parameters
    ----------
        n (Union(int, list)): int なら使う BIT のサイズ。list ならそのlistで BIT を初期化する
    '''
    def __init__(self, x, d=0):
        if isinstance(x, int):
            self.size = x
            self.tree = [d for _ in range(self.size + 1)]
        elif isinstance(x, list):
            self.size = len(x)
            self.tree = [d for _ in range(self.size + 1)]
            self.build(x)
        else:
            raise TypeError

    def build(self, arr):
        """
        初期化されたあとのBITをリストの値に設定する

        Parameters
        ----------
            arr (list): 元のlsit

        Raises
        ------
            TypeError: 入力はlistでないといけないことに注意してください。
        """
        if not isinstance(arr, list):
            raise TypeError
        for num, x in enumerate(arr):
            self.add(num, x)

    def sum(self, i):
        '''[0,i) の和'''
        if i < 0:
            return 0
        s = self.tree[0]
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
        return s

    def add(self, i, a):
        i += 1
        '''i番目の要素にaを足す'''
        if(i == 0):
            return
        while (i <= self.size):
            self.tree[i] += a
            i += (i & -i)

    def lower_bound(self, w):
        '''[0,i]の和 >= w をみたす最小の index
        Examples
        ----------
        >>> bit = BIT([1,0,0,1,0,1,0])
        >>> bit.lower_bound(1)
        0
        >>> bit.lower_bound(2)
        3
        >>> bit.lower_bound(3)
        5
        '''
        if w <= 0:
            return -1
        x = 0
        k = 1 << (self.size.bit_length() - 1)
        while k:
            if x + k <= self.size and self.tree[x + k] < w:
                w -= self.tree[x + k]
                x += k
            k >>= 1
        return x

    def getKthNum(self, w):
        '''k番目(k = 0, 1, ...)に小さい数を返す'''
        w += 1
        return self.lower_bound(w)

    def upper_bound(self, w):
        w += 0.00000000001
        return self.lower_bound(w)

    def query(self, l, r):
        '''[l, r)の和を求める
        >>> bit = BIT([1,2,3,4,5])
        >>> bit.query(1,4)
        9
        >>> bit.query(0,2)
        3
        '''
        return self.sum(r) - self.sum(l)

    # 出力関係（デバッグのみに用いる）
    def __getitem__(self, item):
        if not isinstance(item, int):
            _tmp = item.indices(self.size + 1)
            return [self.sum(i + 1) - self.sum(i) for i in range(_tmp[0], _tmp[1], _tmp[2])]
        else:
            return self.sum(item + 1) - self.sum(item)
    def __str__(self):
        return str(self[0:self.size])
# END CUT HERE

class sqrtDecomposition():
    def __init__(self, N):
        self.BASE = int(sqrt(N))
        self.size = 0
        self.a = [[] for i in range(ceil(N / self.BASE))]
        self.b = BIT(ceil(N / self.BASE))

    def insert(self, i):
        self.size += 1
        idx = bisect.bisect_left(self.a[i // self.BASE], i)
        self.a[i // self.BASE].insert(idx, i)
        self.b.add(i // self.BASE, 1)
        return (i // self.BASE, idx)

    def _next(self, key, idx1, idx2):
        if key >= self.size:
            return (None, None)
        if len(self.a[idx1]) - 1 == idx2:
            idx = self.b.lower_bound(key + 1)
            return (idx, 0)
        else:
            return (idx1, idx2 + 1)

    def _prev(self, key, idx1, idx2):
        if key <= 0:
            return (None, None)
        if idx2 == 0:
            idx = self.b.lower_bound(key)
            return (idx, len(self.a[idx]) - 1)
        else:
            return (idx1, idx2 - 1)

    def get(self, left, right):
        left += 1
        right += 1
        idx1, idx2 = None, None
        for key in range(left, right):
            # debug(key, self.size)
            if key <= 0 or key > self.size:
                yield (None, None)
                continue
            if not idx1:
                idx1 = self.b.lower_bound(key)
                idx2 = key - self.b.sum(idx1) - 1
            else:
                idx1, idx2 = self._next(key - 1, idx1, idx2)
            yield (idx1, idx2)

def main():
    # N = 10**6
    # P = [i for i in range(N)]
    # random.shuffle(P)
    N = ii()
    P = lmi()
    t = sqrtDecomposition(N)
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    # debug(L)
    ans = 0
    for num, i in enumerate(L):
        c = t.insert(i)
        idx = t.b.sum(c[0]) + c[1]
        l = [-1] * 4
        l[1] = t._prev(idx, *c)
        l[0] = t._prev(idx - 1, *l[1])
        l[2] = t._next(idx + 1, *c)
        l[3] = t._next(idx + 2, *l[2])
        # debug(idx, l[0], l[1], l[2], l[3])
        for j in range(4):
            if l[j][0] is not None:
                l[j] = t.a[l[j][0]][l[j][1]]
            else:
                if j >= 2:
                    l[j] = N
                else:
                    l[j] = -1

        # debug(l[0], l[1], l[2], l[3])
        ans += (abs(i - l[1]) * abs(l[3] - l[2]) + abs(l[1] - l[0]) * abs(l[2] - i)) * (N - num)
    print(ans)
    return


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
        import cProfile
        cProfile.run('main()', sort=1)
    else:
        main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
import random
import bisect
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class BIT:
    '''
    BinaryIndexedTreeのクラス。0-indexed に統一してあるので0からn-1までの配列と思って使える。

    Parameters
    ----------
        n (Union(int, list)): int なら使う BIT のサイズ。list ならそのlistで BIT を初期化する
    '''
    def __init__(self, x, d=0):
        if isinstance(x, int):
            self.size = x
            self.tree = [d for _ in range(self.size + 1)]
        elif isinstance(x, list):
            self.size = len(x)
            self.tree = [d for _ in range(self.size + 1)]
            self.build(x)
        else:
            raise TypeError

    def build(self, arr):
        """
        初期化されたあとのBITをリストの値に設定する

        Parameters
        ----------
            arr (list): 元のlsit

        Raises
        ------
            TypeError: 入力はlistでないといけないことに注意してください。
        """
        if not isinstance(arr, list):
            raise TypeError
        for num, x in enumerate(arr):
            self.add(num, x)

    def sum(self, i):
        '''[0,i) の和'''
        if i < 0:
            return 0
        s = self.tree[0]
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
        return s

    def add(self, i, a):
        i += 1
        '''i番目の要素にaを足す'''
        if(i == 0):
            return
        while (i <= self.size):
            self.tree[i] += a
            i += (i & -i)

    def lower_bound(self, w):
        '''[0,i]の和 >= w をみたす最小の index
        Examples
        ----------
        >>> bit = BIT([1,0,0,1,0,1,0])
        >>> bit.lower_bound(1)
        0
        >>> bit.lower_bound(2)
        3
        >>> bit.lower_bound(3)
        5
        '''
        if w <= 0:
            return -1
        x = 0
        k = 1 << (self.size.bit_length() - 1)
        while k:
            if x + k <= self.size and self.tree[x + k] < w:
                w -= self.tree[x + k]
                x += k
            k >>= 1
        return x

    def getKthNum(self, w):
        '''k番目(k = 0, 1, ...)に小さい数を返す'''
        w += 1
        return self.lower_bound(w)

    def upper_bound(self, w):
        w += 0.00000000001
        return self.lower_bound(w)

    def query(self, l, r):
        '''[l, r)の和を求める
        >>> bit = BIT([1,2,3,4,5])
        >>> bit.query(1,4)
        9
        >>> bit.query(0,2)
        3
        '''
        return self.sum(r) - self.sum(l)

    # 出力関係（デバッグのみに用いる）
    def __getitem__(self, item):
        if not isinstance(item, int):
            _tmp = item.indices(self.size + 1)
            return [self.sum(i + 1) - self.sum(i) for i in range(_tmp[0], _tmp[1], _tmp[2])]
        else:
            return self.sum(item + 1) - self.sum(item)
    def __str__(self):
        return str(self[0:self.size])
# END CUT HERE

class sqrtDecomposition():
    def __init__(self, N):
        self.BASE = 100
        self.size = 0
        self.a = [[] for i in range(ceil(N / self.BASE))]
        self.b = BIT(ceil(N / self.BASE))

    def insert(self, i):
        self.size += 1
        idx = bisect.bisect_left(self.a[i // self.BASE], i)
        self.a[i // self.BASE].insert(idx, i)
        self.b.add(i // self.BASE, 1)
        return (i // self.BASE, idx)

    def _next(self, key, idx1, idx2):
        if key >= self.size:
            return (None, None)
        if len(self.a[idx1]) - 1 == idx2:
            idx = self.b.lower_bound(key + 1)
            return (idx, 0)
        else:
            return (idx1, idx2 + 1)

    def _prev(self, key, idx1, idx2):
        if key <= 0:
            return (None, None)
        if idx2 == 0:
            idx = self.b.lower_bound(key)
            return (idx, len(self.a[idx]) - 1)
        else:
            return (idx1, idx2 - 1)

    def get(self, left, right):
        left += 1
        right += 1
        idx1, idx2 = None, None
        for key in range(left, right):
            # debug(key, self.size)
            if key <= 0 or key > self.size:
                yield (None, None)
                continue
            if not idx1:
                idx1 = self.b.lower_bound(key)
                idx2 = key - self.b.sum(idx1) - 1
            else:
                idx1, idx2 = self._next(key - 1, idx1, idx2)
            yield (idx1, idx2)

def main():
    # N = 10**6
    # P = [i for i in range(N)]
    # random.shuffle(P)
    N = ii()
    P = lmi()
    t = sqrtDecomposition(N)
    L = [0 for i in range(N)]
    for i in range(N):
        L[P[i] - 1] = i
    L.reverse()
    # debug(L)
    ans = 0
    for num, i in enumerate(L):
        c = t.insert(i)
        idx = t.b.sum(c[0]) + c[1]
        l = [-1] * 4
        l[1] = t._prev(idx, *c)
        l[0] = t._prev(idx - 1, *l[1])
        l[2] = t._next(idx + 1, *c)
        l[3] = t._next(idx + 2, *l[2])
        # debug(idx, l[0], l[1], l[2], l[3])
        for j in range(4):
            if l[j][0] is not None:
                l[j] = t.a[l[j][0]][l[j][1]]
            else:
                if j >= 2:
                    l[j] = N
                else:
                    l[j] = -1

        # debug(l[0], l[1], l[2], l[3])
        ans += (abs(i - l[1]) * abs(l[3] - l[2]) + abs(l[1] - l[0]) * abs(l[2] - i)) * (N - num)
    print(ans)
    return


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
        import cProfile
        cProfile.run('main()', sort=1)
    else:
        main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  # 要素の追加
        layer1, layer0 = self.layer1, self.layer0
        if self.rand_depth():
            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 で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

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

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

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

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        raise NotImplementedError  # 地味に実装が悩ましい

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


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

main()