Limak 是一只爱玩的小熊。今天他玩的是摧毁方块塔。他连续建造了n座塔。第 i 座塔由相同的块组成。为便于说明,请参阅第一个示例的图片。
Limak将重复以下操作,直到所有东西都被摧毁。
如果一个块具有全部四个邻居,即它的每一侧(上、左、下、右)都与其他块或地板相邻,则该块被称为内部块。否则,块就是边界。在一次操作中,利马克摧毁了所有边界方块。他的爪子速度非常快,他同时摧毁了所有这些方块。
Limak 已准备好开始。你的任务是计算他需要多少次操作才能摧毁所有塔。
输入
第一行包含单个整数 n (1 ≤ n ≤ 105)。
第二行包含 n 个空格分隔的整数 h1, h2, ..., hn (1 ≤ hi ≤ 109) — 塔的大小。
输出
打印摧毁所有塔所需的操作数。
示例
输入 #1
6 2 1 4 6 2 2
输出 #1
3
输入 #2
7 3 3 3 1 3 3 3
输出 #2
2
注意
下图显示了第一个示例测试的所有三个操作。每次边界块都用红色标记。