Sawtooth approximation#1449
A sequence of integers B_0, B_1, \dots, B_{N-1} is defined as a sawtooth sequence if it satisfies the following conditions:
For all even indices from to N-2 inclusive, B_i < B_{i+1}.
For all odd indices from to N-2 inclusive, B_i > B_{i+1}.
You are given a sequence of integers A_0, A_1, \dots, A_{N-1}. Your task is to approximate this sequence as closely as possible with a sawtooth sequence B_0, B_1, \dots, B_{N-1}. The degree of approximation is measured by the sum |B_0 - A_0| + |B_1 - A_1| + \dots + |B_{N-1} - A_{N-1}|. The best approximation is the one where this sum is minimized.
The first line contains an integer (3 \leq N \leq 100), representing the size of the array. The next lines contain the sequence A_0, A_1, \dots, A_{N-1} (1 \leq A_i \leq 1000000000), which needs to be approximated by a sawtooth sequence.
Output a single integer, which is the minimal possible degree of approximation of the sequence A_0, A_1, \dots, A_{N-1} by a sawtooth sequence B_0, B_1, \dots, B_{N-1}.
Example 1