题目描述

zpy 又发明了一个小游戏，炸方块。

有 $n$ 列方块，每列方块分别有 $h_i$ 个方块构成，也就是高度为 $h_i$。zpy 定义边缘方块是这样的：如果一个方块上下左右都有接触到其他方块或地面，就算内部方块，否则就是边缘方块。这个游戏每次可以将当前的边缘方块全部炸掉，这些炸掉的方块就会消失，余下剩余的方块，这个时候，剩余方块里不少方块变成边缘方块，又可以被炸掉了。

zpy 现在想知道的是，给定初始方块情况，最少炸多少次方块会全部消失？

输入格式

第一行输入 $n$，$1\le n\le 10^5$。

第二行输入 $n$ 个整数 $h_i$，$1\le h_i\le 10^9$。

输出格式

输出操作次数。

6
2 1 4 6 2 2

3

7
3 3 3 1 3 3 3

2