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

예를 들어, 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를 볼록하게 만들기 위한 연산의 최소 횟수를 출력한다.

예제 입력 1

6
6 5 1 5 3 3

예제 출력 1

7

예제 입력 2

4
3 0 1 4

예제 출력 2

0

예제 입력 3

7
1 1 1 0 2 2 2

예제 출력 3

5