Дома у Вадима почти закончился ремонт, и сейчас ему осталось лишь полностью дозабить N гвоздей в одну доску. Эти гвозди расположены в один ряд, поэтому они пронумерованы числами от 1 до N, i-й гвоздь недозабит на l_i сантиметров. У Вадима есть в арсенале молоток. Этот молоток имеет размер двух гвоздей, то есть один удар будет всегда над одной парой соседних гвоздей. Если один гвоздь из пары недозабит больше, то он забивается на 1 см. Если оба гвоздя одинаково недозабиты, то они оба забиваются на 1 см. Ремонт надо закончить как можно быстрее, ведь вечером у Вадима дома тусовочка. Помогите ему найти наименьшее количество ударов, за которое можно дозабить все гвозди.

В первой строке дано целое число N — количество гвоздей в доске (2 ≤ N ≤ 10⁵).

Во второй строке даны N целых чисел l_i — количество сантиметров, на которое не дозабит i-й гвоздь (1 ≤ l_i ≤ 10⁹).

Выведите наименьшее количество ударов, за которое можно дозабить все гвозди.