Пилообразная аппроксимация

Последовательность из 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]|. Лучшим считается такое приближение, для которого степень приближения является минимальной.

Входные данные

В первой строке задано число N (3 ≤ N ≤ 100) - размер массива, в последующих N строках описано исходную последовательность A[0], A[1], ..., A[N-1] (1 ≤ A[i] ≤ 1000000000), пилообразное приближение которой необходимо найти.

Выходные данные

Целое число, равное минимальной возможной степени приближения последовательности A[0], A[1], ..., A[N-1] при помощи пилообразной последовательности B[0], B[1], ..., B[N-1].

Примеры