题目描述

圣诞节的联欢活动上，还有一个拆积木塔的游戏。游戏的规则是，提供 $n$ 座积木塔，所有积木塔都是由棱长为 $1$ 的正方体积木块搭建而成，积木塔从左到右编号从 $1$ 到 $n$，第 $i$ 座塔的长和宽都是 $1$，高度为 $h_i$（恰好由 $h_i$ 个积木块搭建而成）。将积木块分为两类，如果上下左右四个方向都有相邻的积木块或地面，则称为内部块；否则称为边界块。规定摧毁积木塔的每一次操作为：摧毁当前局面下所有的边界块。你的任务是：计算同学们需要多少次操作才能摧毁所有积木塔中的所有积木块。

输入格式

第一行仅有一个整数 $n$（$1 \leq n \leq 10^5$），第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$1 \leq h_i \leq 10^9$），分别表示第 $i$ 座塔的大小。

输出格式

输出所需操作数以摧毁所有积木塔中的所有积木块。

6
2 1 4 6 2 2

3

7
3 3 3 1 3 3 3

2

提示

样例 1 解释：每次边界块都用红色标记。第一次操作后，还剩下四个块，第二次操作后只剩下一个。这最后一个块在第三次操作中被摧毁。