В Баку есть здания, которые вышли из строя. На их месте должны быть построены новые здания. Для этого нужно разрушить старые здания.

Барыш является специалистом по разрушению дорог. У него есть супер-робот, который разрушает здания.

В городе имеются n расположенных рядом друг с другом зданий. Чтобы их разрушить, Барыш воспользовался своим роботом.

Каждое из зданий состоит из расположенных друг над другом блоков. Робот должен разрушить все эти блоки. За один ход робот может разрушить все внешние блоки. По этим данным вычислите количество ходов, за которое робот разрушит все здания.

Блок называется внешним, если хотя бы в одном из его 4 направлений (влево, вправо, вниз, вверх) имеется пустое место (для ясности смотрите на картинку).

Входные данные

В первой строке дано количество зданий n (1 ≤ n ≤ 105). На следующей строке даны высоты зданий h1, h2, ... , hn (1 ≤ hi ≤ 109).

Выходные данные

Вывести одно целое число - количество ходов, которое требуется для разрушения всех зданий.

Данная картинка поясняет первый пример