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

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

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

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

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

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

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

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

산 깎기 (S) timer 4초 memory 128MB

산 깎기 (S) 4초 128MB