Жабенятко Біллі#3904
Жабенятко Біллі сиділо на камені і милувалось заходом сонця, коли зрозуміло, що зголодало. Воно озирнулось і з подивом помітило, що в струмку коло нього копошаться мошки. Струмок являє собою пряму, на якій розміщено і камінь, на якому сидить Біллі. Жабенятко було дуже голодне, і тому захотіло з'їсти усіх мошок. У Біллі дуже довгий язик, тому воно може, не зістрибуючи з каменя, з'їсти довільну мошку (але лише одну за раз).
Проте висовувати язика на великі відстані не так уже й просто, жабенятко на кожен сантиметр висуненого язика витрачає одну одиницю енергії. Кожен раз, коли Біллі з'їдає мошку з якоїсь точки відбувається наступне: усі мошки, які сидять ліворуч від з'їденої мошки, і усі мошки, які сидять праворуч від неї з острахом відстрибують від місця подій на один сантиметр вздовж струмка. Мошки, які сидять у тій же точці, що і з'їдена, настільки шоковані цією подією, що не рухаються.
Якщо мошка у якийсь момент часу стрибає на камінь, де сидить Біллі, то Біллі тут же з'їдає її не витрачаючи енергії. При цьому інші мошки не переміщуються.
Жабенятко Біллі хоче зрозуміти — яку мінімальну кількість одиниць енергії йому потрібно для того, щоб з'їсти усіх мошок. Допоможіть йому це з'ясувати.
У першому рядку вхідного файлу задано одне натуральне число (1 \le n \le 100000) — кількість мошок. У другому рядку вхідного файлу задано натуральних чисел — відстань кожної з мошок до каменя. Відомо, що усі мошки знаходяться на одній прямій по одну сторону від каменя. Відстані задано у порядку неспадання. Відстані не перевищують 10^9.
Виведіть одне число — мінімальну кількість одиниць енергії, яка потрібна Біллі, щоб з'їсти усіх мошок.
Приклад 1