问题描述

有 $N$ 个人排成一列坐在 $M$ 个座位上。

当第 $i$ 个人所坐座位的两边至少有 $A_i$ 个连续空座时，求 $M$ 的最小值。

这里不能保证 $N$ 个人按照给定的顺序排列。(13:38)

输入

输入从标准输入中给出，具有以下格式：

$N$

$A_1$ $A_2$ .. $A_N$

• 第一行是人的数量 $N(1≦N≦100000)$。
• 第二行是以空格分隔的 $N$ 个整数 $A_i(1≦A_i≦1000000000)$，表示给定的 $A_i$ 值。

评分标准

此问题不设置部分分，只有全部通过了测试用例才能得到100分。

输出

输出考虑到座位数 $M$ 的最小值。末尾要加换行符。

输入示例1

3
2 3 2

输出示例1

13

输入示例2

5
6 6 9 7 4

输出示例2

46

输入示例3

10
10 6 6 10 3 8 8 9 4 2

输出示例3

86