风化

有 $n$ 列岩块从左到右排成一排，第 $i$ 列有 $h_i$ 个岩块自下而上堆叠。所有岩块放置在地面上，地面不会风化。

现在所有暴露的岩块同时开始风化。一个岩块是暴露的，当且仅当它的左方、右方、上方三个方向中至少有一个方向没有紧邻的岩块（地面不算岩块）。

每个岩块恰好需要一分钟完全风化。一个岩块完全风化后，风化作用会立刻传到与它上下左右紧邻的、尚未风化的岩块。

求所有岩块全部风化所需的分钟数。如果没有岩块，输出 $0$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $h_1, h_2, \ldots, h_n$。

输出格式

一行一个整数，表示所有岩块全部风化所需的分钟数。

提示

本题共 $20$ 组数据。

对于前 $30\%$ 的数据，$n \le 1000$，$h_i \le 1000$。

对于前 $60\%$ 的数据，$n \le 200000$，$h_i \le 1000$。

对于 $100\%$ 的数据，$1 \le n \le 200000$，$0 \le h_i \le 10^9$。