問題
このパンケーキは$2$Lの水を蓄えると崩壊するが上手に水を与えると$2$つに分裂する。 あなたは毎日$1$Lの水を上手に全てのパンケーキに与えてパンケーキを養殖しています（趣味）。 あなたは毎日水を与えた後にmi個のパンケーキを食べたくなります。 食べたくなったらもう仕方がない欲望を満たすかパンケーキがなくなるまで食べてしまいます。 パンケーキは水を多く蓄えている方がおいしいので水を多く蓄えたものから食べてしまいます。 初日は水を$0$L蓄えたパンケーキが$1$つだけある状態でn日後の水を与える前ににパンケーキがいくつあるかもとめよ。 初日から水を与え分裂したパンケーキは$0$Lの水を蓄えているものと$1$Lの水を蓄えているものに分裂する。分裂したパンケーキは翌日から水を与えるものとする。
入力
n m0 . . . mn-1
1行目に日数0≦n≦90があたえられる。
2行目〜n+1行目までi日に食べたくなるパンケーキの個数0≦mi≦1000000000が与えられる。
出力
n日後の水を与える前にパンケーキが何個か1行で出力せよ。出力の最後に改行を入れること。
入出力例
入力例1
3 0 1 0
出力例1
1
入力例2
10 0 0 1 0 0 3 0 0 4 0
出力例2
23