Buggy python submission (verdict: Time Limit Exceeded):

class BIT:
    """
    1-indexed
    """
    def __init__(self, size):
        self.size = size
        self.data = [0] * (size + 1)

    def add(self, index, value=1):
        while index <= self.size:
            self.data[index] += value
            index += index & (-index)

    def sum(self, index):
        """
        右端含める
        """
        ret = 0
        while index:
            ret += self.data[index]
            index -= index & (-index)
        return ret

    def search(self, val):
        """
        x_1 + ... x_i >= val を満たす最小のi
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)  # 一番上の長さ

        while step:
            if i + step <= self.size and s + self.data[i + step] < val:
                i += step
                s += self.data[i]
            step //= 2
        return i + 1


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

    pToI = {p : i for i, p in enumerate(P[1:], 1)}
    tree = BIT(N)

    ans = 0
    for p in range(1, N + 1)[:: -1]:
        i = pToI[p]
        left = tree.sum(i)  # 左にある個数
        tree.add(i)
        right = (N - p) - left  # 右にある個数(処理済みの内，左にないものの個数)

        # L1 < L2 < p < R1 < R2
        L1 = tree.search(left - 1) if left >= 2 else 0
        L2 = tree.search(left) if left >= 1 else 0
        R1 = tree.search(left + 2) if right >= 1 else N + 1
        R2 = tree.search(left + 3) if right >= 2 else N + 1

        cnt = 0
        if L2 != 0:
            cnt += (L2 - L1) * (R1 - i)
        if R1 != 0:
            cnt += (R2 - R1) * (i - L2)

        ans += cnt * p

    print(ans)

sol()

Fixed submission:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index):
        while index <= self.size:
            self.tree[index] += 1
            index += index & (-index)

    def sum(self, index):
        ret = 0
        while index:
            ret += self.tree[index]
            index -= index & (-index)
        return ret

    def search(self, value):
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step //= 2
        return i + 1

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

    ans = 0
    pToIndex = {p : i for i, p in enumerate(P[1:], 1)}
    tree = BIT(N)

    for p in range(1, N + 1)[:: -1]:
        c = pToIndex[p]
        left = tree.sum(c)
        tree.add(c)

        right = N - p - left

        a = tree.search(left - 1) if left >= 2 else 0
        b = tree.search(left) if left >= 1 else 0
        d = tree.search(left + 2) if right >= 1 else N + 1
        e = tree.search(left + 3) if right >= 2 else N + 1

        cnt = 0
        if b != 0:
            cnt += (b - a) * (d - c)
        if d != 0:
            cnt += (e - d) * (c - b)

        ans += cnt * p

    print(ans)

sol()

Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N = int(input())
INF = 10**18
P = list(map(int, input().split()))
I = [-1] * (N + 1)
tree = UnionFind(N + 2)

for i, p in enumerate(P, start=1):
    I[p] = i

ans = 0
used = [False] * (N + 2)
for p in range(1, N):
    i = I[p]

    # p 未満の範囲 [i - left, i + right]
    left = tree.sizeOfSameRoot(i - 1) if used[i - 1] else 0
    right = tree.sizeOfSameRoot(i + 1) if used[i + 1] else 0

    cnt = 0
    leftMx = i - (left + 1)
    if leftMx >= 1 and not used[leftMx]:
        L = tree.sizeOfSameRoot(leftMx - 1) if (leftMx - 1) >= 0 and used[leftMx - 1] else 0
        cnt += (L + 1) * (right + 1)
    rightMx = i + (right + 1)
    if rightMx <= N and not used[rightMx]:
        R = tree.sizeOfSameRoot(rightMx + 1) if (rightMx + 1) <= N and used[rightMx + 1] else 0
        cnt += (left + 1) * (R + 1)
    ans += cnt * p

    used[i] = True
    if used[i - 1]:
        tree.union(i, i - 1)
    if used[i + 1]:
        tree.union(i, i + 1)
print(ans)


Fixed submission:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index):
        while index <= self.size:
            self.tree[index] += 1
            index += index & (-index)

    def sum(self, index):
        ret = 0
        while index:
            ret += self.tree[index]
            index -= index & (-index)
        return ret

    def search(self, value):
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step //= 2
        return i + 1

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

    ans = 0
    pToIndex = {p : i for i, p in enumerate(P[1:], 1)}
    tree = BIT(N)

    for p in range(1, N + 1)[:: -1]:
        c = pToIndex[p]
        left = tree.sum(c)
        tree.add(c)

        right = N - p - left

        a = tree.search(left - 1) if left >= 2 else 0
        b = tree.search(left) if left >= 1 else 0
        d = tree.search(left + 2) if right >= 1 else N + 1
        e = tree.search(left + 3) if right >= 2 else N + 1

        cnt = 0
        if b != 0:
            cnt += (b - a) * (d - c)
        if d != 0:
            cnt += (e - d) * (c - b)

        ans += cnt * p

    print(ans)

sol()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index):
        while index <= self.size:
            self.tree[index] += 1
            index += index & (-index)

    def sum(self, index):
        ret = 0
        while index:
            ret += self.tree[index]
            index -= index & (-index)
        return ret

    def search(self, value):
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step //= 2
        return i + 1

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

    ans = 0
    pToIndex = {p : i for i, p in enumerate(P[1:], 1)}
    tree = BIT(N)

    for p in range(1, N + 1)[:: -1]:
        c = pToIndex[p]
        left = tree.sum(c)
        tree.add(c)

        right = N - p - left

        a = tree.search(left - 1) if left >= 2 else 0
        b = tree.search(left) if left >= 1 else 0
        d = tree.search(left + 2) if right >= 1 else N + 1
        e = tree.search(left + 3) if right >= 2 else N + 1

        cnt = 0
        if b != 0:
            cnt += (b - a) * (d - c)
        if d != 0:
            cnt += (e - d) * (c - b)

        ans += cnt * p

    print(ans)

sol()

Fixed submission:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index):
        while index <= self.size:
            self.tree[index] += 1
            index += index & (-index)

    def sum(self, index):
        ret = 0
        while index:
            ret += self.tree[index]
            index -= index & (-index)
        return ret

    def search(self, value):
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step //= 2
        return i + 1

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

    ans = 0
    pToIndex = {p : i for i, p in enumerate(P[1:], 1)}
    tree = BIT(N)

    for p in range(1, N + 1)[:: -1]:
        c = pToIndex[p]
        left = tree.sum(c)
        tree.add(c)

        right = N - p - left

        a = tree.search(left - 1) if left >= 2 else 0
        b = tree.search(left) if left >= 1 else 0
        d = tree.search(left + 2) if right >= 1 else N + 1
        e = tree.search(left + 3) if right >= 2 else N + 1

        cnt = 0
        if b != 0:
            cnt += (b - a) * (d - c)
        if d != 0:
            cnt += (e - d) * (c - b)

        ans += cnt * p

    print(ans)

sol()