스케이트 연습

문제

스케이트 코스에 N개의 중간 지점이 있다. 각 중간 지점 i에는 통과 속력 제한 Vi가 있다.

시작과 끝의 속력은 0이다. 속력은 자유롭게 올릴 수 있지만, 한 구간당 최대 1만큼만 낮출 수 있다. (내리막 제한)

각 중간 지점을 통과하는 속력의 합을 최대화하시오.

제한

• 1 ≤ N ≤ 500,000