CF573B.Bear and Blocks

Limak is a little bear who loves to play. Today he is playing by destroying block towers. He built n towers in a row. The i-th tower is made of h__i identical blocks. For clarification see picture for the first sample.

Limak will repeat the following operation till everything is destroyed.

Block is called internal if it has all four neighbors, i.e. it has each side (top, left, down and right) adjacent to other block or to the floor. Otherwise, block is boundary. In one operation Limak destroys all boundary blocks. His paws are very fast and he destroys all those blocks at the same time.

Limak is ready to start. You task is to count how many operations will it take him to destroy all towers.

Limak 是一只可爱的小熊，热爱玩耍。今天，他正在通过摧毁积木塔来玩耍。他在一行中搭建了 $n$ 座塔。第 $i$ 座塔由 $h_i$ 个完全相同的积木组成。具体示意图参见第一个样例的图片。

Limak 将不断重复以下操作，直到所有塔都被彻底摧毁。

若一个积木块具有全部四个邻接块（即其上、左、下、右四个方向均与另一个积木块或地面相邻），则称该积木块为内部块；否则称为边界块。在一次操作中，Limak 会摧毁所有边界块。他的爪子非常迅速，能够同时摧毁所有这些边界块。

Limak 已准备就绪，即将开始。你的任务是计算他摧毁所有塔所需的总操作次数。

The first line contains single integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers _h_1, _h_2, ..., h__n (1 ≤ h__i ≤ 109) — sizes of towers.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。

第二行包含 $n$ 个以空格分隔的整数 $h_1, h_2, \dots, h_n$（$1 \leq h_i \leq 10^9$）—— 各塔的高度。

Print the number of operations needed to destroy all towers.

输出摧毁所有塔所需的运算次数。

The picture below shows all three operations for the first sample test. Each time boundary blocks are marked with red color.

After first operation there are four blocks left and only one remains after second operation. This last block is destroyed in third operation.

下图展示了第一个样例测试中的全部三种操作。每次操作中，边界方块均以红色标出。

第一次操作后剩余四个方块，第二次操作后仅剩一个方块。该最后一个方块在第三次操作中被摧毁。