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

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		larger = len(largeind)-2
		smaller = 1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		# largeind.insert(larger,target)
		largeind[larger:larger]=[target]

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

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

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		largeind.append(target)
		largeind.sort(reverse=True)
		ti = largeind.index(target)

		L1ind = largeind[ti-1]
		L2ind = largeind[ti-2]
		R1ind = largeind[ti+1]
		R2ind = largeind[ti+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = np.array(list(map(int,input().strip().split())))

	ips = np.argsort(P)[::-1]
	psort = np.sort(P)[::-1]

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[i]

		larger = len(largeind)-2
		smaller = 1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*psort[i]

	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

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

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		larger = len(largeind)-2
		smaller = 1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

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

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		larger = len(largeind)
		smaller = -1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

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

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	pp = []
	for i, val in enumerate(P):
		pp.append([i,val])
	pp.sort(key=lambda x:x[1],reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = pp[i][0]
		L1ind, L2ind = -1, -1
		R1ind, R2ind = N, N

		larger = len(largeind)
		smaller = -1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*pp[i][1]

	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

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

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	pp = []
	for i, val in enumerate(P):
		pp.append([i,val])
	pp.sort(key=lambda x:x[1],reverse=True)

	x = 0
	largeind = []
	for i in range(N):
		target = pp[i][0]
		L1ind, L2ind = -1, -1
		R1ind, R2ind = N, N

		larger = len(largeind)
		smaller = -1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		if larger-1>=0:
			L1ind = largeind[larger-1]
		if larger-2>=0:
			L2ind = largeind[larger-2]
		if larger+1<=len(largeind)-1:
			R1ind = largeind[larger+1]
		if larger+2<=len(largeind)-1:
			R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*pp[i][1]

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

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

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	x = 0
	for L in range(N):
		L1ind, L2ind = -1, -1
		R1ind, R2ind = N, N
		indt = L-1
		while L2ind==-1 and indt>=0:
			if P[indt]>=P[L]:
				if L1ind==-1:
					L1ind = indt
				elif L2ind==-1:
					L2ind = indt
			indt -= 1

		indt = L+1
		while R2ind==N and indt<=N-1:
			if P[indt]>=P[L]:
				if R1ind==N:
					R1ind = indt
				elif R2ind==N:
					R2ind = indt		
			indt += 1

		x += ((L1ind-L2ind)*(R1ind-L) + (L-L1ind)*(R2ind-R1ind))*P[L]

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

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

# def add(x,y):
# 	return x+y

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	x = 0
	first = 0
	second = 0
	second_list = []
	scnd_acml = []
	for L in range(N):
		if P[L]>first:
			second = first
			first = P[L]
		elif P[L]>second:
			second = P[L]

		if L!=0:
			x = x+second
			second_list.append(second)
			scnd_acml.append(0)
			scnd_acml = list(map(lambda x:x+second, scnd_acml))

	for L in range(1,N-1):
		first = 0
		second = 0
		for i in range(N-L):
			ind = L+i
			if P[ind]>first:
				second = first
				first = P[ind]
			elif P[ind]>second:
				second = P[ind]

			if second==second_list[ind-1]:
				x = x+scnd_acml[ind-1]
				break
			else:
				x = x+second
		

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()

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

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	x = 0
	for L in range(N-1):
		first = P[L]
		second = 0
		for i in range(1,N-L):
			ind = L+i
			if P[ind]>first:
				second = first
				first = P[ind]
			elif P[ind]>second:
				second = P[ind]

			x = x+second

	print(x)

if __name__ == "__main__":
    main()


Fixed submission:
import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

if __name__ == "__main__":
    main()