빗물 모으기

어둡고 폭풍이 몰아치는 밤이었다. 비는 내리고 또 내렸다.

루시는 이 빗물을 조금이라도 받아 두고 싶지만 가진 재료가 넉넉하지 않다. 루시에게는 높이가 제각각인 기둥이 여러 개 있다. 기둥의 높이는 모두 정수이고 밑면은 1 × 1이다. 루시는 기둥을 원하는 순서로 한 줄로 세우고, 앞면과 뒷면은 판자로 막을 만큼 재료가 있다. 그래서 기둥 사이의 빈 공간은 모두 빗물로 채워진다. 비는 넘칠 만큼 내리고, 넘친 물은 땅으로 스며든다.

세워 놓은 기둥을 왼쪽부터 $a_1, a_2, \dots, a_N$이라고 하자. $i$번째 기둥 위에 고이는 물의 높이는 $\min(\max(a_1, \dots, a_i),\ \max(a_i, \dots, a_N)) - a_i$이고, 받아 낸 빗물의 양은 이 값을 모든 $i$에 대해 더한 값이다.

예를 들어 높이가 1, 5, 2, 1, 4인 기둥이 있으면 옆에서 본 모습이 다음과 같도록 세울 수 있다.

 *
 *  *
 *  *
 ** *
*****

이때 빗물 5만큼이 고인다. 물이 찬 칸은 R로 표시했다.

 *
 *RR*
 *RR*
 **R*
*****

같은 기둥 다섯 개로 6만큼을 받아 낼 수도 있다.

 *
 *RR*
 *RR*
**RR*
*****

높이가 5, 1, 5, 1, 5인 기둥이라면 다음 배치가 8만큼을 받아 낸다.

*R*R*
*R*R*
*R*R*
*R*R*
*****

5, 1, 4, 1, 5를 다음과 같이 세우면 9만큼이 고인다.

*RRR*
*R*R*
*R*R*
*R*R*
*****

루시에게는 높이가 $h_1, h_2, \dots, h_N$인 기둥 $N$개가 있고, 어떻게 세우든 기둥을 전부 쓴다. 루시가 받아 낼 수 있는 빗물의 양을 모두 구하라.

첫째 줄에 기둥의 개수 $N$이 주어진다 ($2 \le N \le 500$).

둘째 줄에 기둥의 높이 $h_1, h_2, \dots, h_N$이 주어진다 ($1 \le h_i \le 50$). $h_i$는 $i$번째 기둥의 높이다.

받아 낼 수 있는 빗물의 양을 모두 증가하는 순서로 한 줄에 공백 하나로 구분해 출력한다.