B. Мишка и кубики
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лимак — маленький мишка, который любит играть. Он строит башенки из кубиков, а потом рушит их.

Он возвёл n башен, расположенных в ряд, i-я башня сделана из hi одинаковых кубиков. (смотрите иллюстрацию к первому примеру).

Лимак повторит следующую операцию, пока конструкция не разрушится целиком.

Кубик называется внутренним, если у него есть все четыре соседа, то есть если каждая его сторона (левая, правая, верхняя или нижняя) примыкает к другому кубику или к полу. В противном случае, кубик считается граничным. За одну операцию Лимак одновременно разрушает все граничные кубики.

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

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

В первой строке записано единственное целое число n (1 ≤ n ≤ 105).

Во второй строке записано n целых чисел через пробел h1, h2, ..., hn (1 ≤ hi ≤ 109) — размеры башен.

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

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

Примеры
Входные данные
6
2 1 4 6 2 2
Выходные данные
3
Входные данные
7
3 3 3 1 3 3 3
Выходные данные
2
Примечание

Приведенная ниже иллюстрация показывает все три операции для первого теста. Каждый раз граничные кубики окрашены красным.

После первой операции остается четыре кубика, а после второй операции остается только один. Этот последний кубик уничтожается в третьей операции.