有$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$。