eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

Input data

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

Output data

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

Examples

Input example #1
5
1
100
99
101
7
Output example #1
0
Author Ivan Metelsky