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

Послідовність з 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].

Приклади