Офіс для домашніх тварин#12996

Офіс для домашніх тварин

1 секунда
512 мегабайтів
Середня

Solidgate — це захоплива фінтех-компанія, яка цінує інновації, технології та розумних людей! Тому вони запросили Джеррі приєднатися до команди. Але всі знають: де Джеррі, там і Том. Щоб переконатися, що Том достатньо кмітливий, у Solidgate вирішили дати йому дуже складне завдання перед тим, як дозволити приєднатися до компанії.

Том проходить співбесіду дистанційно.

Допоможіть Тому розв’язати таку задачу, щоб отримати своє місце в Solidgate:

Масив називається хорошим, якщо він не містить двох однакових сусідніх елементів. За одну операцію ви можете вибрати будь-який елемент масиву та збільшити або зменшити його на . Знайдіть мінімальну кількість операцій, необхідних, щоб зробити заданий масив хорошим.

Вхідні дані

У першому рядку задано ціле число — довжина масиву.

У другому рядку задано цілих чисел a_1, a_2, \ldots, a_n.

1 \le n \le 10^5,

0 \le a_i \le 10^9.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість операцій, необхідних, щоб зробити масив хорошим.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі заданий масив можна перетворити на масив [0, 1, -1, 0] за дві операції.

У другому прикладі заданий масив можна перетворити на масив [5, 4, 7, 6, 7, 3, 4] за три операції.