William 和他的朋友们正在露营，并收集了一些木块。天黑前，他们将这些木块从左到右堆叠成 $N$ 堆。第 $i$ 堆有 $W_i$ 个木块垂直堆叠在一起。
每个木块完全烧毁需要恰好一分钟。一旦一个木块完全烧毁，火势会蔓延到所有与它相邻的木块（即左侧、右侧、上方和下方的木块），并开始燃烧它们。
William 从最外层的木块开始点火，即那些左侧、右侧或上方没有木块的木块。请确定所有木块完全烧毁所需的总分钟数。
输入格式
第一行包含一个整数 $N$ ($1 \le N \le 200\,000$)。第二行包含 $N$ 个整数，表示每一堆木块的数量 $W_i$ ($0 \le W_i \le 10^9$)。
输出格式
输出一行，表示所有木块完全烧毁所需的分钟数。
样例
输入 1
5 2 3 4 2 3
输出 1
3
说明 1
下图展示了燃烧过程：
第 0 分钟到第 3 分钟的燃烧过程示意图
输入 2
13 2 5 6 6 4 3 4 3 1 2 4 8 4
输出 2
4
输入 3
3 1 0 2
输出 3
1
输入 4
1 0
输出 4
0