14281번 - 볼록 수열

문제

정수 수열 x[0], x[1], ..., x[N-1]이 볼록이 되려면 모든 1 ≤ i ≤ N-2에 대해서, x[i-1]+x[i+1] ≥ 2*x[i]를 만족해야 한다. 또, 길이가 1, 2인 수열은 항상 볼록하다.

예를 들어, 7, 3, 4, 5, 7과 4, 2, 1, 3은 볼록하지만, 4, 3, 1, 2와 5, 7, 3은 볼록하지 않다.

수열 A가 주어졌을 때, 수열을 볼록하게 만드는 최소 연산 횟수를 구하는 프로그램을 작성하시오. 연산은 인덱스 i를 고르고, a[i]를 a[i]-1로 바꾸는 연산만 허용된다.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 50)이, 둘째 줄에 수열 A가 입력으로 주어진다. (0 ≤ a[i] ≤ 10⁹)

출력

수열 A를 볼록하게 만들기 위한 연산의 최소 횟수를 출력한다.

제한

힌트