Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())

c = n // 4

ans = 0

for i in range(c+1):
    d = (n - i*4) // 7
    for v in range(d+1):
        buy = i*4 + v*7
        check = buy - n
        
        if check == 0:
            ans = "Yes"
        
if ans == "Yes":
    print("Yes")
else:
    print("No")

Fixed submission:
n, k = list(map(int, input().split(" ")))
ans = n % k
if ans > 0:
    print(1)
else:
    print(0)

Buggy python submission (verdict: Runtime Error):
n = int(input())

c = n // 4

ans = 0

for i in range(c+1):
    d = (n - i*4) // 7
    for v in range(d+1):
        buy = i*4 + v*7
        check = buy - n
        
        if check == 0:
            ans = "Yes"
            break
    if ans == "Yes":
        break
        

if ans == "Yes":
    print("Yes")
else:
    print("No")

Fixed submission:
n, k = list(map(int, input().split(" ")))
ans = n % k
if ans > 0:
    print(1)
else:
    print(0)

Buggy python submission (verdict: Runtime Error):
n = int(input())

c = n // 4

ans = 0

for i in range(c+1):
    d = (n - i*4) // 7
    for v in range(d+1):
        buy = i*4 + v*7
        check = buy - n
        
        if check == 0:
            ans = "Yes"
            break
    if ans == "Yes":
        break
        

if ans == "Yes":
    print("Yes")
else:
    print("No")

Fixed submission:
n, k = list(map(int, input().split(" ")))
ans = n % k
if ans > 0:
    print(1)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())

a_ind = [i for i, v  in enumerate(s) if v == "A"]
z_ind = [i for i, v in enumerate(s) if v == "Z"]
z_ind = [i for i in z_ind if i > min(a_ind)]

ans = z_ind[-1] - a_ind[0] + 1

print(ans)

Fixed submission:
s = list(input())

a_ind = [i for i, v  in enumerate(s) if v == "A"]
z_ind = [i for i, v in enumerate(s) if v == "Z"]


ans = z_ind[-1] - a_ind[0] + 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = input().split()
for i in range(len(A)):
    A[i] = int(A[i])
A.sort()

answer = A[0]
overl = False

for i in range(N-1):
    answer *= A[i+1]
    if answer > 10**18:
        overl = True
        break

if overl:
    print("-1")
else:
    print(answer)

Fixed submission:
S = input().split()

A = int(S[0])
B = int(S[1])

print(A*B)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = input().split()
for i in range(len(A)):
    A[i] = int(A[i])

answer = A[0]
overl = False

for i in range(N-1):
    answer *= A[i+1]

if answer > 10**18:
    print("-1")
else:
    print(answer)

Fixed submission:
N = int(input())
org = input().split()
for i in range(len(org)):
    org[i] = int(org[i])
A = sorted(org)

answer = A[0]
overl = False

for i in range(N-1):
    answer *= A[i+1]
    if answer > 10**18:
        overl = True
        break

if overl:
    print("-1")
else:
    print(answer)
Buggy python submission (verdict: Runtime Error):
import math
 
A,B,H,M=map(int,input().split(" "))
 
hour=[A*math.cos(math.radians(H*30+M/2)),A*math.sin(math.radians(H*30+M/2))]
minute =[B*math.cos(math.radians(M*6)),B*math.sin(math.radians(M*6))]
if (hour[0]>=0 and minute[0]>=0) or (hour[0]<0 and minute[0]<0):
    a=minute[0]-hour[0]
else:
    a=abs(minute[0])+abs(hour[0])
    
if (hour[1]>=0 and minute[1]>=0) or (hour[1]<0 and minute[1]<0):
    b=minute[1]-hour[1]
else:
    b=abs(minute[1])+abs(hour[1])    
print('{:.16f}'.format(math.sqrt(pow(a,2)+pow(b,2))))

Fixed submission:
N = int(input())

if N%10==2 or N%10==4 or N%10==5 or N%10==7 or N%10==9:
    print('hon')
elif N%10==0 or N%10==1 or N%10==6 or N%10==8:
    print('pon')
else:
    print('bon')

Buggy python submission (verdict: Runtime Error):
N = int(input())

if N%10==2 orN%10==4 or N%10==5 or N%10==7 or N%10==9:
    print('hon')
elif N%10==0 orN%10==1 or N%10==6 or N%10==8:
    print('pon')
else:
    print('bon')

Fixed submission:
N = int(input())

if N%10==2 or N%10==4 or N%10==5 or N%10==7 or N%10==9:
    print('hon')
elif N%10==0 or N%10==1 or N%10==6 or N%10==8:
    print('pon')
else:
    print('bon')
Buggy python submission (verdict: Time Limit Exceeded):
import math

# doubling

n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))
doubling =[[0 for _ in range(n + 1)] for _ in range(62)]

for i in range(62):
	for j in range(1, n + 1):
		if i == 0:
			doubling[i][j] = nums[j]
		else:
			doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]

cur = 1
for i, x in enumerate(bin(k)[2:][::-1]):
	if x == "1":
		cur = doubling[i][cur]
print(cur)


Fixed submission:
import sys
n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))

visited = [0 for _ in range(n + 1)]
path = [1]
cur = 1
visited[1] = 1
for i in range(k):
	cur = nums[cur]
	path.append(cur)
	if visited[cur] == 1:
		for idx, val in enumerate(path):
			if val == cur:
				break
		# print(k, idx, path)
		# print((k - idx) % (len(path) - idx - 1))
		print(path[idx + (k - idx) % ((len(path) - idx - 1))])
		sys.exit()
	else:
		visited[cur] = 1
print(cur)

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

# doubling

n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))
doubling =[[0 for _ in range(n + 1)] for _ in range(int(math.log2(k)) + 1)]

for i in range(len(doubling)):
	for j in range(1, n + 1):
		if i == 0:
			doubling[i][j] = nums[j]
		else:
			doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]

cur = 1
for i, x in enumerate(bin(k)[2:][::-1]):
	if x == "1":
		cur = doubling[i][cur]
print(cur)


Fixed submission:
import sys
n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))

visited = [0 for _ in range(n + 1)]
path = [1]
cur = 1
visited[1] = 1
for i in range(k):
	cur = nums[cur]
	path.append(cur)
	if visited[cur] == 1:
		for idx, val in enumerate(path):
			if val == cur:
				break
		# print(k, idx, path)
		# print((k - idx) % (len(path) - idx - 1))
		print(path[idx + (k - idx) % ((len(path) - idx - 1))])
		sys.exit()
	else:
		visited[cur] = 1
print(cur)
Buggy python submission (verdict: Time Limit Exceeded):
def naive(a, b, n):
	ans = 0
	for i in range(1, n + 1):
		ans = max(ans, int((a * i) / b) - a * int(i / b))
	return ans

def main(a, b, n):
	ans = 0
	tmp = []
	for i in range(max(n + 1 - a * 10 - 1, 1), n + 1):
		ans = max(ans, int((a * i) / b) - a * int(i / b))
	return ans


n = 10000
for a in range(1, 10):
	for b in range(1, 100):
		if naive(a, b, n) != main(a, b, n):
			print(a, b, naive(a, b, n), main(a, b, n))

a, b, n = list(map(int, input().split()))
print(main(a, b, n))

Fixed submission:
def val(a, b, x):
	return (a * x) // b - a * (x // b)

def naive(a, b, n):
	ans = 0
	for i in range(1, n + 1):
		ans = max(ans, val(a, b, i))
	return ans

def main(a, b, n):
		return max(val(a, b, n), val(a, b, max((n // b) * b - 1, 1)), val(a, b, max(n - 1, 0)))

# n = 10
# for a in range(1, 1000):
# 	for b in range(1, 1000):
# 		if naive(a, b, n) != main(a, b, n):
# 			print(a, b, naive(a, b, n), main(a, b, n))

a, b, n = list(map(int, input().split()))
print(main(a, b, n))
Buggy python submission (verdict: Runtime Error):
print([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51][int(input())])

Fixed submission:
print([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51][int(input()) - 1])
Buggy python submission (verdict: Runtime Error):
import sys
n, m = list(map(int, input().split()))
res = [list(map(int, input().split())) for _ in range(m)]

ans = [-1 for _ in range(n)]

for r in res:
	if ans[r[0] - 1] >= 0:
		if ans[r[0] - 1] != r[1]:
			print(-1)
			sys.exit()
	ans[r[0] - 1] = r[1]

flag = 0
for i in range(3):
	if ans[i] == -1:
		if flag:
			ans[i] = 0
		else:
			ans[i] = 1
	else:
		flag = 1


print("".join([str(a) for a in ans]))

Fixed submission:
import sys
n, m = list(map(int, input().split()))
res = [list(map(int, input().split())) for _ in range(m)]

ans = [-1 for _ in range(n)]



if n == 1:
	tmp = 0
	for i in range(m):
		tmp += res[i][1]
	if tmp == 0:
		print(0)
		sys.exit()

for r in res:
	if ans[r[0] - 1] >= 0:
		if ans[r[0] - 1] != r[1]:
			print(-1)
			sys.exit()
	ans[r[0] - 1] = r[1]

#print(res)
#print(ans)
flag = 0
for i in range(n):
	if ans[i] == -1:
		if flag:
			ans[i] = 0
		else:
			ans[i] = 1
	if i == 0 and ans[i] == 0:
		print(-1)
		sys.exit()
	else:
		flag = 1


print("".join([str(a) for a in ans]))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
ex = [(x + 1) / 2 for x in nums]

ans = sum(ex[:k])
for i in range(1, n - k + 2):
	ans = max(ans, sum(ex[i:i + k]))

print(ans)

Fixed submission:
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
ex = [(x + 1) / 2 for x in nums]

cur = sum(ex[:k])
ans = cur
for i in range(0, n - k):
	cur = cur + ex[i + k] - ex[i]
	ans = max(ans, cur)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10 ** 9 + 7

def naive_main(nums):
    n = len(nums)
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            ans += nums[i] ^ nums[j]
    return ans

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

# s

"""
0 0 0 1
0 0 1 0
0 0 1 0
0 1 0 0
1 0 0 0

4, 4, 6, 4

32 16 12 4
"""

max_len = len(bin(max(nums))) - 2

counter = [0 for _ in range(max_len)]
for i in range(n):
    ss = bin(nums[i])[2:]
    ss = "0" * (max_len - len(ss)) + ss
    for j in range(len(ss)):
        if ss[j] == "1":
            counter[j] += 1

# print(n)
# print(counter)
ans = 0
for i in range(max_len):
    c = counter[max_len - 1 - i]
    ans += (c * (n - c) * (2 ** i)) % mod

print(int(ans) % mod)
#print(naive_main(nums))



Fixed submission:
mod = 10 ** 9 + 7

def naive_main(nums):
    n = len(nums)
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            ans += nums[i] ^ nums[j]
    return ans

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

# s

"""
0 0 0 1
0 0 1 0
0 0 1 0
0 1 0 0
1 0 0 0

4, 4, 6, 4

32 16 12 4
"""

max_len = len(bin(max(nums))) - 2

counter = [0 for _ in range(max_len)]
for i in range(n):
    ss = bin(nums[i])[2:]
    ss = "0" * (max_len - len(ss)) + ss
    for j in range(len(ss)):
        if ss[j] == "1":
            counter[j] += 1

# print(n)
# print(counter)
ans = 0
for i in range(max_len):
    c = counter[max_len - 1 - i]
    ans += (c * (n - c) * (2 ** i)) % mod

print(int(ans) % mod)
#print(naive_main(nums))
Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7
n = int(input())
nums = list(map(int, input().split()))

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * len([y for y in n_colors if x == y])) % mod
	n_colors[n_colors.index(x)] += 1

print(cnt)

Fixed submission:
mod = 10 ** 9 + 7
n = int(input())
nums = list(map(int, input().split()))

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * len([y for y in n_colors if x == y])) % mod
	if cnt == 0:
		break
	n_colors[n_colors.index(x)] += 1

print(cnt)

Buggy python submission (verdict: Runtime Error):
import collections
mod = 10 ** 9 + 7

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

# import numpy.random as rd
# n = 1000
# raw_nums = list(rd.randint(low=0, high=3, size=n))
# print(raw_nums)
# nums = [0] + [len([x for x in raw_nums[:i] if x == raw_nums[i]]) for i in range(1, n)]

# print(n, raw_nums, nums)

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * collections.Counter(n_colors)[x]) % mod
	n_colors[n_colors.index(x)] += 1

print(cnt)

Fixed submission:
mod = 10 ** 9 + 7
n = int(input())
nums = list(map(int, input().split()))

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * len([y for y in n_colors if x == y])) % mod
	if cnt == 0:
		break
	n_colors[n_colors.index(x)] += 1

print(cnt)

Buggy python submission (verdict: Runtime Error):
import collections
mod = 1000000007

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

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * collections.Counter(n_colors)[x]) % mod
	n_colors[n_colors.index(x)] += 1

print(cnt)

Fixed submission:
mod = 10 ** 9 + 7
n = int(input())
nums = list(map(int, input().split()))

n_colors = [0, 0, 0]

cnt = 1
for x in nums:
	cnt = (cnt * len([y for y in n_colors if x == y])) % mod
	if cnt == 0:
		break
	n_colors[n_colors.index(x)] += 1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n, t = list(map(int, input().split()))
dishes = [list(map(int, input().split())) for _ in range(n)]

dishes.sort(key = lambda x: (x[0], -x[1]))
#print(dishes)

# dp[i][j]はi番目までの品物から時間の和がj以下なるように選んだときの価値の和の最大値を表す。
dp = [[-1 for _ in range(t + 1)] for _ in range(n + 1)]

for j in range(t):
	dp[0][j] = 0

for i in range(n):
	for j in range(t):
		if j - dishes[i][0] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - dishes[i][0]] + dishes[i][1])
		else:
			dp[i + 1][j] = dp[i][j]
	dp[i + 1][t] = max(dp[i][t], dp[i][t - 1] + dishes[i][1])

#print(dp)
print(dp[-1][-1])

Fixed submission:
n, t = list(map(int, input().split()))
dishes = [list(map(int, input().split())) for _ in range(n)]

dishes.sort(key = lambda x: (x[0], -x[1]))
#print(dishes)

# dp[i][j]はi番目までの品物から時間の和がj以下なるように選んだときの価値の和の最大値を表す。
dp = [[-1 for _ in range(t + 1)] for _ in range(n + 1)]

for j in range(t):
	dp[0][j] = 0

for i in range(n):
	for j in range(t):
		if j - dishes[i][0] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - dishes[i][0]] + dishes[i][1])
		else:
			dp[i + 1][j] = dp[i][j]
	dp[i + 1][t] = max(dp[i][t], dp[i][t - 1] + dishes[i][1])

#print(dp)
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
hs = [0] + list(map(int, input().split())) 


max_val = sum([max(hs[i + 1] - hs[i], 0) for i in range(n)])
dp = [[max_val for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):	
		dp[i][j] = min([dp[i - 1][l] + max(hs[j] - hs[l], 0) for l in range(j)])

print(min([dp[n - k][l] for l in range(n + 1)]))

Fixed submission:
n, k = list(map(int, input().split()))
hs = [0] + list(map(int, input().split())) 


max_val = sum([max(hs[i + 1] - hs[i], 0) for i in range(n)])
dp = [[max_val for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):	
		dp[i][j] = min([dp[i - 1][l] + max(hs[j] - hs[l], 0) for l in range(j)])

print(min([dp[n - k][l] for l in range(n + 1)]))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

def prime_factorize(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a

def calc_dist(x, y):
	return abs(x - 1) + abs(y - 1)

n = int(input())
ll = prime_factorize(n)

min_dist = 10 ** 12
for bb in itertools.product([0, 1], repeat = len(ll)):
	l = 1
	r = 1
	for i in range(len(ll)):
		if bb[i] == 1:
			l *= ll[i]
		else:
			r *= ll[i]
	#print(bb, l, r, calc_dist(l, r))
	min_dist = min(min_dist, calc_dist(l, r))
print(min_dist)

Fixed submission:
import itertools
import collections

def prime_factorize(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a

def calc_dist(x, y):
	return abs(x - 1) + abs(y - 1)

n = int(input())
ll = prime_factorize(n)
c = collections.Counter(ll)
kk = list(c.keys())
vv = list(c.values())
pp = [list(range(vv[i] + 1)) for i in range(len(kk))]

min_dist = 10 ** 12
# print(c)
# print(kk)
# print(vv)
for bb in itertools.product(*pp):
	l = 1
	r = 1
	for i in range(len(kk)):
		l *= max(kk[i] ** bb[i], 1)
		r *= max(kk[i] ** (vv[i] - bb[i]), 1)
	#print(bb, l, r, calc_dist(l, r))
	min_dist = min(min_dist, calc_dist(l, r))
print(min_dist)

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

def prime_factorize(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a

def calc_dist(x, y):
	return abs(x - 1) + abs(y - 1)

n = int(input())
ll = prime_factorize(n)

min_dist = 10 ** 12
for bb in itertools.product([0, 1], repeat = len(ll)):
	l = 1
	r = 1
	for i in range(len(ll)):
		if bb[i] == 1:
			l *= ll[i]
		else:
			r *= ll[i]
	#print(bb, l, r, calc_dist(l, r))
	min_dist = min(min_dist, calc_dist(l, r))
print(min_dist)

Fixed submission:
import itertools
import collections

def prime_factorize(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a

def calc_dist(x, y):
	return abs(x - 1) + abs(y - 1)

n = int(input())
ll = prime_factorize(n)
c = collections.Counter(ll)
kk = list(c.keys())
vv = list(c.values())
pp = [list(range(vv[i] + 1)) for i in range(len(kk))]

min_dist = 10 ** 12
# print(c)
# print(kk)
# print(vv)
for bb in itertools.product(*pp):
	l = 1
	r = 1
	for i in range(len(kk)):
		l *= max(kk[i] ** bb[i], 1)
		r *= max(kk[i] ** (vv[i] - bb[i]), 1)
	#print(bb, l, r, calc_dist(l, r))
	min_dist = min(min_dist, calc_dist(l, r))
print(min_dist)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ss = input()

max_cnt = 0
for i in range(1, n):
    cnt = 0
    for j in range(n - i):
        if ss[j] == ss[j + i]:
            cnt += 1
            max_cnt = max(cnt, max_cnt)
            if cnt == i:
                break
        else:
            cnt = 0

print(max_cnt)

Fixed submission:
n = int(input())
ss = input()

max_cnt = 0
for i in range(1, n):
    cnt = 0
    for j in range(n - i):
        if ss[j] == ss[j + i]:
            cnt += 1
            max_cnt = max(cnt, max_cnt)
            if cnt == i:
                break
        else:
            cnt = 0

print(max_cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ss = input()

ab = "abcdefghijklmnopqrstuvwxyz"
xx = [ab.index(s) for s in ss]

#print(xx)
cnt = 0
max_cnt = 0
i = 0
while i < n:
    j = i + 1
    while j < n:
        if xx[i] == xx[j]:
            while j + cnt < n and i + cnt < j:
                if xx[i + cnt] == xx[j + cnt]:
                    cnt += 1
                else:
                    break
            max_cnt = max(max_cnt, cnt)
            #print(xx[i:(i + cnt)], xx[j:(j + cnt)], i, j, cnt)
            cnt = 0
            j = j + cnt + 1

        else:
            j += 1
            if j >= n - 1:  
                break
    #print(i, j, cnt)
    i += 1
print(max_cnt)

Fixed submission:
n = int(input())
ss = input()

max_cnt = 0
for i in range(1, n):
    cnt = 0
    for j in range(n - i):
        if ss[j] == ss[j + i]:
            cnt += 1
            max_cnt = max(cnt, max_cnt)
            if cnt == i:
                break
        else:
            cnt = 0

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

n = int(input())
xx = list(map(int, input().split()))
pp = [(xx[i], i + 1) for i in range(n)]
pp.sort(reverse = True)

larger = [0, 0, pp[0][1], n + 1, n + 1]
ans = 0

for i in range(1, n):
	idx = bisect.bisect_left(larger, pp[i][1])

	ans += (larger[idx - 1] - larger[idx - 2]) * (larger[idx] - pp[i][1]) * pp[i][0]
	ans += (pp[i][1] - larger[idx - 1]	) * (larger[idx + 1] - larger[idx]) * pp[i][0]
	larger.insert(idx, pp[i][1])

print(ans)

Fixed submission:

def main():
	n = int(input())
	xx = list(map(int, input().split()))

	pp = [(xx[i], i + 1) for i in range(n)]
	pp.sort(key=lambda x: x[0])
	# print(xx)
	# print(pp)

	left = [0, 0] + [i + 1 for i in range(n)]
	right = [i + 1 for i in range(n)] + [n + 1, n + 1]
	ans = 0
	for i in range(n):

		ori_num, ori_ind = pp[i]
		l1 = left[ori_ind]
		l2 = left[l1]
		r1 = right[ori_ind]
		r2 = right[r1]

		# print("ori_num, ori_ind, l1, l2, r1, r2")
		# print(ori_num, ori_ind, l1, l2, r1, r2)
		# print(left)
		# print(right)

		ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

		right[l1] = r1
		left[r1] = l1

	print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
pp = list(map(int, input().split()))


def sub(pp):
	m = len(pp)
	ans = 0
	for i in range(m - 1):
		for j in range(i + 1, m):
			#print(i, j)
			ans += sorted(pp[i:(j + 1)], reverse = True)[1]
	return ans

def calc(a, b):
	if b - a < 1:
		return 0
	elif b - a == 1:
		return min(pp[b], pp[a])
	else:
		pn = sorted(pp[a:(b + 1)], reverse = True)
		f = pp.index(pn[0])
		s = pp.index(pn[1])
		if f > s:
			ans = calc(a, f - 1) + calc(s + 1, b) - calc(s + 1, f - 1) + pp[s] * ((s - a + 1) * (b - f + 1))
		else:
			ans = calc(a, s - 1) + calc(f + 1, b) - calc(f + 1, s - 1) + pp[s] * ((f - a + 1) * (b - s + 1))
		#print(a, b, f, s,  ans)
		return ans


#print(sub(pp))
print(calc(0, n - 1))

Fixed submission:

def main():
	n = int(input())
	xx = list(map(int, input().split()))

	pp = [(xx[i], i + 1) for i in range(n)]
	pp.sort(key=lambda x: x[0])
	# print(xx)
	# print(pp)

	left = [0, 0] + [i + 1 for i in range(n)]
	right = [i + 1 for i in range(n)] + [n + 1, n + 1]
	ans = 0
	for i in range(n):

		ori_num, ori_ind = pp[i]
		l1 = left[ori_ind]
		l2 = left[l1]
		r1 = right[ori_ind]
		r2 = right[r1]

		# print("ori_num, ori_ind, l1, l2, r1, r2")
		# print(ori_num, ori_ind, l1, l2, r1, r2)
		# print(left)
		# print(right)

		ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

		right[l1] = r1
		left[r1] = l1

	print(ans)

main()