A - 映画館 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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