산 깎기 timer 2초 memory 128MB

정올시에서는 정올시 외곽의 산을 관광지로 개발하려는 계획을 추진 중이다.

시에서는 산을 길게 일자로 N개의 구간으로 나누어서 각 구간의 높이를 측량했다.

정올시는 산을 '뾰족한 모양'으로 다듬으면 관광객을 유치할 수 있을 것으로 보고 있다.

여기서 뾰족한 모양이란 산의 높이 조건이 다음을 만족하는 경우를 말한다.

- i번째 구간의 높이가 a_i라고 하면 위치 t를 하나의 꼭대기로 정해서 모든 1<=i<=N에 대해 a_i = a_t - |t - i|가 되도록 할 수 있다.

- 모든 구간의 높이가 1 이상이다.

시에서는 1의 비용을 들여 한 구간의 높이를 1만큼 높이거나 깎을 수 있다.

뾰족한 산을 만들기 위한 최소 비용을 계산하자.