Лимак — маленький мишка, который любит играть. Он строит башенки из кубиков, а потом рушит их.
Он возвёл 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
Приведенная ниже иллюстрация показывает все три операции для первого теста. Каждый раз граничные кубики окрашены красным.
