Solidgate — це захоплива фінтех-компанія, яка цінує інновації, технології та розумних людей! Тому вони запросили Джеррі приєднатися до команди. Але всі знають: де Джеррі, там і Том. Щоб переконатися, що Том достатньо кмітливий, у Solidgate вирішили дати йому дуже складне завдання перед тим, як дозволити приєднатися до компанії.
Том проходить співбесіду дистанційно.
Допоможіть Тому розв’язати таку задачу, щоб отримати своє місце в Solidgate:
Масив називається хорошим, якщо він не містить двох однакових сусідніх елементів. За одну операцію ви можете вибрати будь-який елемент масиву та збільшити або зменшити його на . Знайдіть мінімальну кількість операцій, необхідних, щоб зробити заданий масив хорошим.
У першому рядку задано ціле число — довжина масиву.
У другому рядку задано цілих чисел a_1, a_2, \ldots, a_n.
1 \le n \le 10^5,
0 \le a_i \le 10^9.
Виведіть одне ціле число — мінімальну кількість операцій, необхідних, щоб зробити масив хорошим.
Example
Example 1
У першому прикладі заданий масив можна перетворити на масив [0, 1, -1, 0] за дві операції.
У другому прикладі заданий масив можна перетворити на масив [5, 4, 7, 6, 7, 3, 4] за три операції.