산 깎기 (S)

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

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

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

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

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

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

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

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

입력

첫 줄에 N (1 \le N \le 10,000)이 주어진다.

둘째 줄에 각 구간의 높이가 일렬로 주어진다. 높이는 1에서 10^9사이의 정수이다.

출력

뾰족한 모양의 산을 만들기 위한 최소 비용을 출력하라.

부분문제

예제1

두 번째, 세 번째, 네 번째 산의 높이를 한 번씩 높여 네 번째 산이 뾰족한 부분이 되는 산을 만들 수 있다.

예제2

세 번째 산을 세 번 깎고 네 번째 산을 한 번 높여 두 번째 산이 뾰족하도록 만들 수 있다. 그림으로 나타내면 아래와 같다.

출처

COCI 2017/2018 Contest #4 (수정)

산 깎기 (S) 4초 128MB