说明

William 和他的朋友们正在露营，并收集了一些木块。夜幕降临前，他们将木块从左到右堆成了 $N$ 摞。第 $i$ 摞有 $W_i$ 个木块上下堆叠在一起。

每个木块恰好需要一分钟燃烧。一旦一个木块完全燃尽，火焰会蔓延到所有与它相邻的木块（即紧邻其左、右、上、下方的木块），并开始燃烧它们。

William 从最外层的木块开始点燃，即那些左、右或上方没有木块的木块。请确定所有木块完全燃尽所需的总分钟数。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 200\,000$）。

第二行包含 $N$ 个整数，表示每摞的木块数量 $W_i$（$0 \le W_i \le 10^9$）。

输出格式

输出一行，表示所有木块完全燃尽所需的分钟数。

5
2 3 4 2 3

3

13
2 5 6 6 4 3 4 3 1 2 4 8 4

4

3
1 0 2

1

1
0

0

提示

样例 1 解释： 下图展示了燃烧过程。

:::align{center} :::

翻译由 DeepSeek V3.2 完成