問題文

$N$ 人の人が一列に並んだ $M$ 個の座席に座っている。

$i(1≦i≦N)$ 番目の人の座っている座席の両側ともに少なくとも $A_i$ 個の空席が連続して存在することが分かっているとき、 $M$ の最小値を求めよ。

$N$ 人の人がこの順番で並んでいるとは限りません。(13:38)

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ .. $A_N$

• 一行目には人の数$N(1≦N≦100000)$が与えられる。
• 二行目には文章中で示された値 $A_i(1≦A_i≦1000000000)$ が空白区切りで与えられる。

配点

この問題に部分点はありません。すべてのテストケースに正解すると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