Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = sum([self.data[i], self.data[i-1]])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = sum([self.data[2*idx+1], self.data[2*idx+2]])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = sum([result, self.data[idx1]])
                if idx2&1 == 1: # idx2が奇数
                    result = sum([result, self.data[idx2]])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = sum([result, self.data[idx1]])
            else: # idx1 + 1 == idx2
                result = sum([result, self.data[idx1], self.data[idx2]])
            
            return result

def find_next(st, idx):
    n = len(st)
    idx_v = st.query(idx, idx)
    right_sum = st.query(idx, n) - idx_v
    if right_sum:
        left = idx
        right = n
        while left + 1 < right:
            mid = (left + right) // 2
            right_sum = st.query(idx, mid) - idx_v
            if right_sum >= 1:
                right = mid
            else:
                left = mid
        return left
    else:
        return n

def find_before(st, idx):
    if idx == 0:
        return -1
    left_sum = st.query(0, idx)
    if left_sum:
        left = 0
        right = idx
        while left + 1 < right:
            mid = (left + right) // 2
            left_sum = st.query(mid, idx)
            if left_sum:
                left = mid
            else:
                right = mid
        return left
    else:
        return -1


N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

a = [0]*N
st = SegmentTree(a)
ans = 0
for i, p in P:
  ir1 = find_next(st, i)
  ir2 = N if ir1==N else find_next(st, ir1)
  il1 = find_before(st, i)
  il2 = -1 if il1==-1 else find_before(st, il1)
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  st.update(i, 1)


print(ans)

Fixed submission:
N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:
    def __init__(self, a, mode='min'):
        if mode == 'min':
            self.padding = float('inf')
            self.func = min
        elif mode == 'max':
            self.padding = -float('inf')
            self.func = max
        elif mode == 'sum':
            self.padding = 0
            self.func = sum
        
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self.func([self.data[i], self.data[i-1]])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self.func([self.data[2*idx+1], self.data[2*idx+2]])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = self.func([result, self.data[idx1]])
                if idx2&1 == 1: # idx2が奇数
                    result = self.func([result, self.data[idx2]])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = self.func([result, self.data[idx1]])
            else: # idx1 + 1 == idx2
                result = self.func([result, self.data[idx1], self.data[idx2]])
            
            return result

def find_next(st, idx):
    n = len(st)
    idx_v = st.query(idx, idx)
    right_sum = st.query(idx, n) - idx_v
    if right_sum:
        left = idx
        right = n
        while left + 1 < right:
            mid = (left + right) // 2
            right_sum = st.query(idx, mid) - idx_v
            if right_sum >= 1:
                right = mid
            else:
                left = mid
        return left
    else:
        return n

def find_before(st, idx):
    if idx == 0:
        return -1
    left_sum = st.query(0, idx)
    if left_sum:
        left = 0
        right = idx
        while left + 1 < right:
            mid = (left + right) // 2
            left_sum = st.query(mid, idx)
            if left_sum:
                left = mid
            else:
                right = mid
        return left
    else:
        return -1


N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

a = [0]*N
st = SegmentTree(a, 'sum')
ans = 0
for i, p in P:
  ir1 = find_next(st, i)
  ir2 = N if ir1==N else find_next(st, ir1)
  il1 = find_before(st, i)
  il2 = -1 if il1==-1 else find_before(st, il1)
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  st.update(i, 1)


print(ans)

Fixed submission:
N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:
    def __init__(self, a, mode='min'):
        if mode == 'min':
            self.padding = float('inf')
            self.func = min
        elif mode == 'max':
            self.padding = -float('inf')
            self.func = max
        elif mode == 'sum':
            self.padding = 0
            self.func = sum
        
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self.func([self.data[i], self.data[i-1]])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self.func([self.data[2*idx+1], self.data[2*idx+2]])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = self.func([result, self.data[idx1]])
                if idx2&1 == 1: # idx2が奇数
                    result = self.func([result, self.data[idx2]])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = self.func([result, self.data[idx1]])
            else: # idx1 + 1 == idx2
                result = self.func([result, self.data[idx1], self.data[idx2]])
            
            return result

def find_next(st, idx):
    n = len(st)
    idx_v = st.query(idx, idx)
    right_sum = st.query(idx, n) - idx_v
    if right_sum:
        left = idx
        right = n
        while left + 1 < right:
            mid = (left + right) // 2
            right_sum = st.query(idx, mid) - idx_v
            if right_sum >= 1:
                right = mid
            else:
                left = mid
        return left
    else:
        return n

def find_before(st, idx):
    if idx == 0:
        return -1
    left_sum = st.query(0, idx)
    if left_sum:
        left = 0
        right = idx
        while left + 1 < right:
            mid = (left + right) // 2
            left_sum = st.query(mid, idx)
            if left_sum:
                left = mid
            else:
                right = mid
        return left
    else:
        return -1


N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

a = [0]*N
st = SegmentTree(a, 'sum')
ans = 0
for i, p in P:
  ir1 = find_next(st, i)
  ir2 = N if ir1==N else find_next(st, ir1)
  il1 = find_before(st, i)
  il2 = -1 if il1==-1 else find_before(st, il1)
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  st.update(i, 1)


print(ans)

Fixed submission:
N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

ans = 0
larger_indexes = [-1, -1, N, N]
for i, p in P:
  idx = bisect.bisect_left(larger_indexes, i)
  ir1, ir2 = larger_indexes[idx], larger_indexes[idx+1]
  il1, il2 = larger_indexes[idx-1], larger_indexes[idx-2]
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  larger_indexes.insert(idx, i)

print(ans)

Fixed submission:
N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

ans = 0
larger_indexes = [-1, -1, N, N]
for i, p in P:
  idx = bisect.bisect_left(larger_indexes, i)
  ir1, ir2 = larger_indexes[idx], larger_indexes[idx+1]
  il1, il2 = larger_indexes[idx-1], larger_indexes[idx-2]
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  bisect.insort(larger_indexes, i)

print(ans)

Fixed submission:
N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

ans = 0
larger_indexes = [-1, -1, N, N]
for i, p in P:
  idx = bisect.bisect_left(larger_indexes, i)
  ir1, ir2 = larger_indexes[idx], larger_indexes[idx+1]
  il1, il2 = larger_indexes[idx-1], larger_indexes[idx-2]
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  bisect.insort(larger_indexes, i)

print(ans)

Fixed submission:
N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)