有$n$堆方块，第$i$堆方块由$h_i$个方块堆积而成。具体可以看样例。

接下来拆方块。一个方块称为内部方块当且仅当他的上下左右都是方块或者是地面。否则方块就是边界方块。每一次操作都要把边界方块拿掉。

问多少次操作之后所有方块会消失。

输入格式

第一行有一个整数n($1\leq n\leq 10^5$)。

第二行有n个整数$h_i$($1\leq h_i\leq 10^9$)，表示第i堆方块的数目。

输出格式

输出使得所有方块消失的操作次数。

样例输入

6
2 1 4 6 2 2

样例输出

3

样例解释

点击查看图片

数据规模

所有数据保证 $1\leq n \leq 10^5, 1 \leq h_i\leq 10^9$。