Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP =[int(i) for i in input().split()]
#n = 10000
#ListP = [i for i in range(n)]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
#ListTPos = [0] * (n+2) + [n+1, n+1]
ListTPos = [0] * (n + 1) + [n+1]
ListTPos[ListPos2[n]] = ListPos2[n]
pos = 0
for i in reversed(range(1,n)):
	posi = ListPos2[i]
	ListTPos[posi] =  posi
	for j in ListTPos[posi+1:]:
		if (j > 0):
			pos = ListPos.index(j)
			ListPos.insert(pos, posi)
			#pos = ListTPos[j]
			break
	l1 = ListPos[pos-1]
	l2 = ListPos[pos-2]
	h1 = ListPos[pos+1]
	h2 = ListPos[pos+2]
	points += i * ((posi-l1)*(h2-h1) + (h1-posi)*(l1-l2))
	#low1 = ListPos[pos] - ListPos[pos-1]
	#low2 = ListPos[pos-1] - ListPos[pos-2]
	#high1 = ListPos[pos+1] - ListPos[pos]
	#high2 = ListPos[pos+2] - ListPos[pos+1]
	#points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
area = list(reversed(range(1,n)))
for i in area:
	ListPos.append(ListPos2[i])
	ListPos.sort()
	pos = ListPos.index(ListPos2[i])
	lh = ListPos[pos]
	l1 = ListPos[pos-1]
	l2 = ListPos[pos-2]
	h1 = ListPos[pos+1]
	h2 = ListPos[pos+2]
	points += i * ((lh-l1)*(h2-h1) + (h1-lh)*(l1-l2))
	#low1 = ListPos[pos] - ListPos[pos-1]
	#low2 = ListPos[pos-1] - ListPos[pos-2]
	#high1 = ListPos[pos+1] - ListPos[pos]
	#high2 = ListPos[pos+2] - ListPos[pos+1]
	#points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
#print(ListPos2)
SetPos = {ListPos2[n]}
for i in reversed(range(1, n)):
	SetPos.add(ListPos2[i])
	ListPos = [0, 0] + sorted(SetPos) + [n+1, n+1]
	pos = ListPos.index(ListPos2[i])
	#print(SetDiff)
	#print(SetPos-SetDiff)
	#print(pos)
	#print(ListPos)
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
#print(ListPos2)
SetPos = {ListPos2[n]}
for i in reversed(range(1, n)):
	SetPos.add(ListPos2[i])
	ListPos = [0, 0] + sorted(SetPos) + [n+1, n+1]
	pos = ListPos.index(ListPos2[i])
	#print(SetDiff)
	#print(SetPos-SetDiff)
	#print(pos)
	#print(ListPos)
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
#print(ListPos2)
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
for i in reversed(range(1, n)):
	SetPos = set(ListPos)
	SetDiff = set(range(0, ListPos2[i]))
	pos = ListPos.index(min(SetPos - SetDiff))
	ListPos.insert(pos, ListPos2[i])
	#print(SetDiff)
	#print(SetPos-SetDiff)
	#print(pos)
	#print(ListPos)
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i
#print(ListPos2)
ListPos = [-1, -1] + [ListPos2[n]] + [n, n]
for i in reversed(range(1, n)):
	tempPos = ListPos2[i]
	while (True):
		tempPos += 1
		if (tempPos in ListPos):
			ListPos.insert(ListPos.index(tempPos), ListPos2[i])
			break
	pos = ListPos.index(ListPos2[i])
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i
#print(ListPos2)
ListPos = [-1, -1] + [ListPos2[n]] + [n, n]
for i in reversed(range(1, n)):
	ListPos = sorted(ListPos + [ListPos2[i]])
	pos = ListPos.index(ListPos2[i])
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP = [n+1] + [int(i) for i in input().split()] + [n+1]
#ListPos = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in (range(0, n-1)):
	countHigh1 = 0
	countHigh2 = 0
	countLow1 = 0
	countLow2 = 0
	j = k = l = ListP.index(i+1)
	#print(j)
	while(True):
		j += 1
		if (ListP[j] > i+1):
			countHigh1 = j - l
			break
	while(True):
		if (j == n+1):
			countHigh2 = 0
			break
		j += 1
		if (ListP[j] > i+1):
			countHigh2 = j - (l + countHigh1)
			break
	while(True):		
		k -= 1
		if (ListP[k] > i+1):
			countLow1 = l - k
			break
	while(True):
		if (k == 0):
			break
		k -= 1
		if (ListP[k] > i+1):
			countLow2 = (l - countLow1) - k
			break
	points += (i+1) * (countLow1 * countHigh2 + countHigh1 * countLow2)
	#print(points, countLow1, countHigh2, countHigh1, countLow2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP = [n+1] + [int(i) for i in input().split()] + [n+1]
#ListPos = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in (range(0, n-1)):
	countHigh1 = 0
	countHigh2 = 0
	countLow1 = 0
	countLow2 = 0
	j = k = ListP.index(i+1)
	#print(j)
	while(True):
		countHigh1 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		if (j == n+1):
			break
		countHigh2 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		countLow1 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	while(True):
		if (k == 0):
			break
		countLow2 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	points += (i+1) * (countLow1 * countHigh2 + countHigh1 * countLow2)
	#print(points, countLow1, countHigh2, countHigh1, countLow2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP = [n+1] + [int(i) for i in input().split()] + [n+1]
ListPos = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in (range(0, n-1)):
	countHigh1 = 0
	countHigh2 = 0
	countLow1 = 0
	countLow2 = 0
	j = k = ListPos[i]
	#print(j)
	while(True):
		countHigh1 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		if (j == n+1):
			break
		countHigh2 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		countLow1 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	while(True):
		if (k == 0):
			break
		countLow2 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	points += (i+1) * (countLow1 * countHigh2 + countHigh1 * countLow2)
	#print(points, countLow1, countHigh2, countHigh1, countLow2)
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP = [int(i) for i in input().split()]
#ListPosPのPositionは1からnまでの値
ListPosP = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in reversed(range(1, n)):
	ListDistPlus = sorted([j - ListPosP[i-1] for j in ListPosP[i:] if j - ListPosP[i-1] > 0])
	ListDistMinus = sorted([j - ListPosP[i-1] for j in ListPosP[i:] if j - ListPosP[i-1] < 0])
	#Plus側のiより大きい値を1つだけ含む部分配列
	if (len(ListDistPlus) == 1):
		ListDistPlus = ListDistPlus + [n+1-(ListPosP[i-1] + 1)]
	if (len(ListDistPlus) == 0):
		ListDistPlus = [n+1-(ListPosP[i-1] + 1), n+1-(ListPosP[i-1] + 1)]
	if (len(ListDistMinus) == 1):
		ListDistMinus = [-(ListPosP[i-1] + 1)] + ListDistMinus
	if (len(ListDistMinus) == 0):
		ListDistMinus = [-(ListPosP[i-1] + 1), -(ListPosP[i-1] + 1)]
	points += i * ((ListDistPlus[1] - ListDistPlus[0]) * (-ListDistMinus[-1]) + (ListDistMinus[-1] - ListDistMinus[-2]) * (ListDistPlus[0]))
	#print(points)デバッグ用
	#print(ListDistMinus[-1], ListDistMinus[-2], ListDistPlus[0], ListDistPlus[1])デバッグ用
print(points)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP = [int(val) for val in input().split()]

l = 0
r = 2
xlr = 0
tempMax = tempMax2 = max2 = 0
while (l < n - 1):
	tempMax2 = min(ListP[l : l + 2])
	xlr += tempMax2
	tempMax = max(ListP[l : l + 2])
	while (r < n):
		if (tempMax2 < ListP[r]):
			if (tempMax < ListP[r]):
				tempMax2 = tempMax
				tempMax = ListP[r]
			else:
				tempMax2 = ListP[r]
		if (tempMax2 == max2):
			xlr += (n - r) * max2
			break
		xlr += tempMax2
		r += 1
	if (l == 0):
		max2 = tempMax2
	l += 1
	r = l + 2
print(xlr)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP = [int(val) for val in input().split()]

l = 0
r = 2
xlr = 0
tempMax = temp2Max = 0
while (l < n - 1):
	temp2Max = min(ListP[l : l + 2])
	xlr += temp2Max
	tempMax = max(ListP[l : l + 2])
	while (r < n):
		if (temp2Max < ListP[r]):
			if (tempMax < ListP[r]):
				temp2Max = tempMax
				tempMax = ListP[r]
			else:
				temp2Max = ListP[r]
		xlr += temp2Max
		r += 1
	l += 1
	r = l + 2
print(xlr)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ListP = [int(val) for val in input().split()]

l = 0
r = 1
TempList = []
xlr = 0
while (l < n - 1):
	while (r < n):
		TempList = ListP[l : r + 1]
		TempList.remove(max(TempList))
		xlr += max(TempList)
		r += 1
	l += 1
	r = l + 1
print(xlr)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)