Задача C. Пилообразная аппроксимация ≡

Условие

Последовательность из N целых чисел B[0], B[1], ..., B[N-1] называется пилообразной, если выполняются следующие два условия:

1. B[i] < B[i+1] для всех четных i от 0 до N-1 включительно.
2. B[i] > B[i+1] для всех нечетных i от 0 до N-1 включительно.

Вам задана произвольная последовательность из N целых чисел A[0], A[1], ..., A[N-1]. Необходимо как можно лучше приблизить ее при помощи пилообразной последовательности B[0], B[1], ..., B[N-1]. Степенью приближения будем считать значение суммы |B[0] - A[0]| + |B[1] - A[1]| + ... + |B[N-1] - A[N-1]|. Лучшим считается такое приближение, для которого степень приближения является минимальной.

Формат входного файла

Формат выходного файла

Ограничения

1. Число N от 3 до 100 включительно.
2. Количество элементов в массиве A равно N.
3. Каждый элемент массива A от 1 до 1000000000 (один миллиард) включительно.
4. Количество тестов не превосходит 50.

Примеры тестов

5
1 100 99 101 7

0

5
101 2 3 1 95

195

10
1 2 3 4 5 6 7 8 9 10

8

3
1 1 1

1

8
257915 131153 654421 649173 247591 85697 736425 80156

1341434