불안정한 탑

HI-TECH 건설의 신입사원 '홍익이'는 천재적인 재능과 넘치는 열정으로 모두의 기대를 한 몸에 받고 있습니다.

최근 그는 $N$개의 최첨단 타워로 구성된 새로운 랜드마크, 'HI-ARC'의 최종 디자인을 맡게 되었습니다.

홍익이는 자신만의 확고한 디자인 철학이 있었습니다.

"가장 위대한 탑이란, 홀로 우뚝 솟은 탑이다!"

그래서 홍익이는 이 철학에 따라, 마음에 드는 탑을 양 옆의 탑보다 한참 높아 보이도록 설계했습니다.

드디어 그랜드 오픈을 하루 앞둔 오늘, 최종 안전 시뮬레이션에서 치명적인 설계 결함이 발견되었습니다! 홍익이의 디자인 철학이 아래와 같은 구조적 불안정성을 가진다는 사실이 밝혀진 것입니다.

$N$개의 탑의 높이를 $A\_1, A\_2, \dots, A\_N$이라고 할 때, 불안정한 탑은 아래와 같습니다.

• 1번째 탑은 2번째 탑보다 높으면 불안정합니다. ($A\_1 > A\_2$)
• $N$번째 탑은 $N-1$번째 탑보다 높으면 불안정합니다. ($A\_N > A\_{N-1}$)
• $k$번째 ($2 \le k \le N-1$) 탑은 양 옆 두 탑의 높이 평균보다 높으면 불안정합니다. ($A\_k > \frac{A\_{k-1} + A\_{k+1}}{2}$)

당신은 홍익이의 사고를 수습해야 하는 안전진단팀장으로서, 하룻밤 안에 이 사태를 수습해야 합니다. 유일한 해결책은 크레인을 동원해 탑의 높이를 낮추는 것입니다.

크레인을 이용하면 탑의 높이를 낮출 수 있습니다. 한 번의 조작에서 어떤 탑이든 높이를 $H$에서 $H-X$로 바꿀 수 있으며, $X$는 정수이고 $1 \le X \le H$입니다. 이때 비용은 $X$만큼 발생합니다. 이러한 조작은 필요한 만큼 여러 번 수행할 수 있습니다.

위 조건 하에서 항상 탑을 안정화시킬 수 있음은 증명할 수 있습니다. 그러나 예산은 한정되어 있기에, 지불하는 비용을 최소화해야 합니다.

홍익이가 남긴 아슬아슬한 설계안을 받아 들고, 모든 탑을 안정시키기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하세요.

첫 번째 줄에 탑의 개수 $N$ ($3 \le N \le 100\\, 000$) 이 주어집니다.

두 번째 줄에 초기 $N$개의 탑의 높이 $A\_1, A\_2, \dots, A\_N$이 공백으로 구분되어 주어집니다.

모든 $A\_k$는 정수이며 $1 \le A\_k \le 10^9$를 만족합니다.

모든 탑을 안정시키기 위해 지불해야 하는 최소 비용을 정수로 출력합니다.