1277번: 빗물 웅덩이

폭이 1인 블록 기둥 N개가 한 줄로 붙어 서 있어요. 비가 많이 내리면 기둥 사이의 움푹한 곳에 빗물이 고여요.

어떤 자리에 고이는 빗물의 높이는, 그 자리를 포함한 왼쪽 기둥들 중 가장 높은 기둥과 그 자리를 포함한 오른쪽 기둥들 중 가장 높은 기둥 가운데 더 낮은 쪽의 높이에서 그 자리 기둥의 높이를 뺀 값이에요.

예를 들어 기둥 높이가 차례대로 3 0 2 0 4이면 자리마다 0, 3, 1, 3, 0만큼 빗물이 고여서 모두 7이에요. 고인 빗물의 양을 모두 더해 보세요.

입력

첫째 줄에 기둥의 수 N이 주어져요. (1 ≤ N ≤ 1,000)

둘째 줄에 왼쪽 기둥부터 차례대로 높이 N개가 공백으로 구분되어 주어져요. (0 ≤ 각 높이 ≤ 10,000)

출력

고인 빗물의 양을 모두 더한 값을 출력해요.

힌트

자리마다 왼쪽 끝과 오른쪽 끝까지 매번 살펴보면 느려요. 왼쪽부터의 가장 높은 기둥과 오른쪽부터의 가장 높은 기둥을 미리 구해 두면 빨라요.