Convex Sequence

Time limit2sMemory limit512 MB

Summary

Subtract 1 from elements of a sequence (N up to 50) so that it becomes convex, minimizing total subtractions.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Math, Implementation
Solved: No attempts yet

Problem

An integer sequence $x_0, x_1, \dots, x_{N-1}$ is convex when $x_{i-1} + x_{i+1} \ge 2 x_i$ holds for every $i$ with $1 \le i \le N-2$ . A sequence of length 1 or 2 is always convex.

For example, 7, 3, 4, 5, 7 and 4, 2, 1, 3 are convex, while 4, 3, 1, 2 and 5, 7, 3 are not.

You are given a sequence $A = a_0, a_1, \dots, a_{N-1}$ . One operation picks an index $i$ and replaces $a_i$ with $a_i - 1$ , and no other operation is allowed. You may pick the same index several times, and an element may become negative. Write a program that finds the minimum number of operations that makes $A$ convex.

Input

The first line contains the size of the sequence, $N$ ( $1 \le N \le 50$ ). The second line contains the integers $a_0, a_1, \dots, a_{N-1}$ ( $0 \le a_i \le 10^9$ ) of the sequence $A$ , separated by spaces.

Output

Print the minimum number of operations that makes $A$ convex on the first line.

Examples3

Example 1
Input
```
6
6 5 1 5 3 3
```
Expected output
```
7
```
Example 2
Input
```
4
3 0 1 4
```
Expected output
```
0
```
Example 3
Input
```
7
1 1 1 0 2 2 2
```
Expected output
```
5
```