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:
class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

N = int(input())
P = list(map(int, input().split()))
I = [-1] * (N+1)
for i, p in enumerate(P):
    I[p] = i
ans = 0
avl = AvlTree(n=N)
for val, (n, idx) in zip(range(N, 0, -1), enumerate(I[N:0:-1], 1)):
    avl.add(idx)
    idx_avl = avl.bisect_left(idx)  # :thinking_face:
    l = avl[idx_avl-1] if idx_avl>0 else -1
    r = avl[idx_avl+1] if idx_avl<n-1 else N
    #print(idx_avl, l, r)
    if idx_avl > 0:
        l2 = avl[idx_avl-2] if idx_avl>1 else -1
        ans += val * (l-l2) * (r-idx)
        #print(f"val * (l-l2) * (r-idx)={val * (l-l2) * (r-idx)}")
    if idx_avl < n-1:
        r2 = avl[idx_avl+2] if idx_avl<n-2 else N
        ans += val * (idx-l) * (r2-r)
        #print(f"val * (idx-l) * (r2-r)={val * (idx-l) * (r2-r)}")
print(ans)

Submission status: Accepted

Solution code:
class WeightBalancedTree:
    def __init__(self, q):
        self.left = [0] * (q + 1)
        self.right = [0] * (q + 1)
        self.weight = [1] * (q + 1)
        self.key = [None] * (q + 1)
        self.last_index = 0
        self.root = 0

# key 未満の最大値
    def search_lower(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] < key:
                ret = self.key[idx]
                idx = self.right[idx]
            else:
                idx = self.left[idx]
        return ret

# key 超過の最小値
    def search_higher(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] > key:
                ret = self.key[idx]
                idx = self.left[idx]
            else:
                idx = self.right[idx]
        return ret

# 要素の挿入
# 重複を考慮しない
# ToDo: 考慮するものも実装する
    def insert(self, key):
        self.last_index += 1
        self.key[self.last_index] = key
        self.weight[self.last_index] = 2
        self.root = self.__recursive_insert(self.root)
        NotImplemented

# insert の再帰実装に用いる
    def __recursive_insert(self, idx):
        if idx == 0:
            return self.last_index
        elif self.key[self.last_index] < self.key[idx]:
            self.left[idx] = self.__recursive_insert(self.left[idx])
            self.__fix(idx)
            return self.__fix_left_bias(idx)
        else:
            self.right[idx] = self.__recursive_insert(self.right[idx])
            self.__fix(idx)
            return self.__fix_right_bias(idx)

# ノードの weight を補正する
    def __fix(self, idx):
        self.weight[idx] = self.weight[self.left[idx]] + \
            self.weight[self.right[idx]]

# 左回転
    def __rotate_left(self, idx):
        right = self.right[idx]
        self.right[idx] = self.left[right]
        self.__fix(idx)
        self.left[right] = idx
        self.__fix(right)
        return right

# 右回転
    def __rotate_right(self, idx):
        left = self.left[idx]
        self.left[idx] = self.right[left]
        self.__fix(idx)
        self.right[left] = idx
        self.__fix(left)
        return left

# 左偏状態の補正
    def __fix_left_bias(self, idx):
        if self.weight[self.right[idx]] << 2 < self.weight[idx]:
            left = self.left[idx]
            if self.weight[self.left[left]] << 2 < self.weight[left]:
                self.left[idx] = self.__rotate_left(left)
            idx = self.__rotate_right(idx)
        return idx

# 右偏状態の補正
    def __fix_right_bias(self, idx):
        if self.weight[self.left[idx]] << 2 < self.weight[idx]:
            right = self.right[idx]
            if self.weight[self.right[right]] << 2 < self.weight[right]:
                self.right[idx] = self.__rotate_right(right)
            idx = self.__rotate_left(idx)
        return idx

# 要素数
    def size(self):
        return self.weight[self.root] - 1

# デバッグ用
    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx != 0:
            self.__dump(self.right[idx], dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print('i:{0},k:{1},l:{2},r:{3},w:{4}'.format(
                idx, self.key[idx], self.left[idx], self.right[idx], self.weight[idx]))
            self.__dump(self.left[idx], dep + 1)


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = WeightBalancedTree(n+2)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Submission status: Accepted

Solution code:
class WeightBalancedTree:
    def __init__(self, q):
        self.left = [0] * (q + 1)
        self.right = [0] * (q + 1)
        self.weight = [1] * (q + 1)
        self.key = [None] * (q + 1)
        self.last_index = 0
        self.root = 0

# key 未満の最大値
    def search_lower(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] < key:
                ret = self.key[idx]
                idx = self.right[idx]
            else:
                idx = self.left[idx]
        return ret

# key 超過の最小値
    def search_higher(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] > key:
                ret = self.key[idx]
                idx = self.left[idx]
            else:
                idx = self.right[idx]
        return ret

# 要素の挿入
# 重複を考慮しない
# ToDo: 考慮するものも実装する
    def insert(self, key):
        self.last_index += 1
        self.key[self.last_index] = key
        self.weight[self.last_index] = 2
        self.root = self.__recursive_insert(self.root)
        NotImplemented

# insert の再帰実装に用いる
    def __recursive_insert(self, idx):
        if idx == 0:
            return self.last_index
        elif self.key[self.last_index] < self.key[idx]:
            self.left[idx] = self.__recursive_insert(self.left[idx])
            self.__fix(idx)
            return self.__fix_left_bias(idx)
        else:
            self.right[idx] = self.__recursive_insert(self.right[idx])
            self.__fix(idx)
            return self.__fix_right_bias(idx)

# ノードの weight を補正する
    def __fix(self, idx):
        self.weight[idx] = self.weight[self.left[idx]] + \
            self.weight[self.right[idx]]

# 左回転
    def __rotate_left(self, idx):
        right = self.right[idx]
        self.right[idx] = self.left[right]
        self.__fix(idx)
        self.left[right] = idx
        self.__fix(right)
        return right

# 右回転
    def __rotate_right(self, idx):
        left = self.left[idx]
        self.left[idx] = self.right[left]
        self.__fix(idx)
        self.right[left] = idx
        self.__fix(left)
        return left

# 左偏状態の補正
    def __fix_left_bias(self, idx):
        if self.weight[self.right[idx]] * 4 < self.weight[idx]:
            left = self.left[idx]
            if self.weight[self.left[left]] * 4 < self.weight[left]:
                self.left[idx] = self.__rotate_left(left)
            idx = self.__rotate_right(idx)
        return idx

# 右偏状態の補正
    def __fix_right_bias(self, idx):
        if self.weight[self.left[idx]] * 4 < self.weight[idx]:
            right = self.right[idx]
            if self.weight[self.right[right]] * 4 < self.weight[right]:
                self.right[idx] = self.__rotate_right(right)
            idx = self.__rotate_left(idx)
        return idx

# 要素数
    def size(self):
        return self.weight[self.root] - 1

# デバッグ用
    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx != 0:
            self.__dump(self.right[idx], dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print('i:{0},k:{1},l:{2},r:{3},w:{4}'.format(
                idx, self.key[idx], self.left[idx], self.right[idx], self.weight[idx]))
            self.__dump(self.left[idx], dep + 1)


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = WeightBalancedTree(n+2)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Submission status: Accepted

Solution code:
class WeightBalancedTree:
    def __init__(self, q):
        self.left = [0] * (q + 1)
        self.right = [0] * (q + 1)
        self.weight = [1] * (q + 1)
        self.key = [None] * (q + 1)
        self.last_index = 0
        self.root = 0

# key 未満の最大値
    def search_lower(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] < key:
                ret = self.key[idx]
                idx = self.right[idx]
            else:
                idx = self.left[idx]
        return ret

# key 超過の最小値
    def search_higher(self, key):
        if key == None:
            return None
        ret = None
        idx = self.root
        while idx != 0:
            if self.key[idx] > key:
                ret = self.key[idx]
                idx = self.left[idx]
            else:
                idx = self.right[idx]
        return ret

# 要素の挿入
# 重複を考慮しない
# ToDo: 考慮するものも実装する
    def insert(self, key):
        self.last_index += 1
        self.key[self.last_index] = key
        self.weight[self.last_index] = 2
        self.root = self.__recursive_insert__(self.root)
        NotImplemented

# insert の再帰実装に用いる
    def __recursive_insert__(self, idx):
        if idx == 0:
            return self.last_index
        elif self.key[self.last_index] < self.key[idx]:
            self.left[idx] = self.__recursive_insert__(self.left[idx])
            self.__fix__(idx)
            return self.__fix_left_bias__(idx)
        else:
            self.right[idx] = self.__recursive_insert__(self.right[idx])
            self.__fix__(idx)
            return self.__fix_right_bias__(idx)

# ノードの weight を補正する
    def __fix__(self, idx):
        self.weight[idx] = self.weight[self.left[idx]] + \
            self.weight[self.right[idx]]

# 左回転
    def __rotate_left__(self, idx):
        right = self.right[idx]
        self.right[idx] = self.left[right]
        self.__fix__(idx)
        self.left[right] = idx
        self.__fix__(right)
        return right

# 右回転
    def __rotate_right__(self, idx):
        left = self.left[idx]
        self.left[idx] = self.right[left]
        self.__fix__(idx)
        self.right[left] = idx
        self.__fix__(left)
        return left

# 左偏状態の補正
    def __fix_left_bias__(self, idx):
        if self.weight[self.right[idx]] * 4 < self.weight[idx]:
            left = self.left[idx]
            if self.weight[self.left[left]] * 4 < self.weight[left]:
                self.left[idx] = self.__rotate_left__(left)
            idx = self.__rotate_right__(idx)
        return idx

# 右偏状態の補正
    def __fix_right_bias__(self, idx):
        if self.weight[self.left[idx]] * 4 < self.weight[idx]:
            right = self.right[idx]
            if self.weight[self.right[right]] * 4 < self.weight[right]:
                self.right[idx] = self.__rotate_right__(right)
            idx = self.__rotate_left__(idx)
        return idx

# 要素数
    def size(self):
        return self.weight[self.root] - 1

# デバッグ用
    def dumb(self):
        self.__dumb__(self.root, 0)

    def __dumb__(self, idx, dep):
        if idx != 0:
            self.__dumb__(self.right[idx], dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print('i:{0},k:{1},l:{2},r:{3},w:{4}'.format(
                idx, self.key[idx], self.left[idx], self.right[idx], self.weight[idx]))
            self.__dumb__(self.left[idx], dep + 1)


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = WeightBalancedTree(n+2)
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Submission status: Accepted

Solution code:
def f_e():
    n, *p = map(int, open(0).read().split())
    p = sorted([(v, i) for i, v in enumerate(p)])
    *l, = range(-1, n-1)
    *r, = range(1, n+1)
    a = 0
    for v, i in p:
        l0, r0 = l[i], r[i]
        l1 = l[l0] if l0>-1 else l0
        r1 = r[r0] if r0<n else r0
        a += ((l0-l1)*(r0-i)+(r1-r0)*(i-l0))*v
        if l0>-1:
            r[l0]=r0
        if r0<n:
            l[r0]=l0
    print(a)

if __name__ == "__main__":
    f_e()