Пилкоподібна апроксимація#1449
Послідовність з цілих чисел B_0, B_1, \dots, B_{N-1} називається пилкоподібною, якщо вона задовольняє таким умовам:
Для всіх парних індексів від до N-2 включно виконується B_i < B_{i+1}.
Для всіх непарних індексів від до N-2 включно виконується B_i > B_{i+1}.
Вам задано послідовність з цілих чисел A_0, A_1, \dots, A_{N-1}. Ваше завдання — якнайточніше наблизити цю послідовність пилкоподібною послідовністю B_0, B_1, \dots, B_{N-1}. Ступінь наближення вимірюється сумою |B_0 - A_0| + |B_1 - A_1| + \dots + |B_{N-1} - A_{N-1}|. Найкращим наближенням є те, для якого ця сума мінімальна.
У першому рядку задано ціле число (3 \leq N \leq 100) — розмір масиву. У наступних рядках задано послідовність A_0, A_1, \dots, A_{N-1} (1 \leq A_i \leq 1000000000), яку потрібно наблизити пилкоподібною послідовністю.
Виведіть одне ціле число — мінімально можливий ступінь наближення послідовності A_0, A_1, \dots, A_{N-1} до пилкоподібної послідовності B_0, B_1, \dots, B_{N-1}.
Приклад 1