AT_codefestival_2015_qualA_b とても長い数列

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-quala/tasks/codefestival_2015_qualA_b 高橋君は長さ $ N $ の数列 $ A\ =\ \{A_1,\ A_2,\ ...,\ A_N\} $ を用意しました。高橋君は数列 $ A $ を元に「とても長い数列」を、以下のような手順で作ろうとしています。 - まず長さ $ 0 $ の数列を用意し、これを $ S $ と呼ぶことにする。 - $ S $、$ A_1 $、$ S $ をこの順につなげた数列を新たな $ S $ とする。 - $ S $、$ A_2 $、$ S $ をこの順につなげた数列を新たな $ S $ とする。 - （中略） - $ S $、$ A_N $、$ S $ をこの順につなげた数列を新たな $ S $ とする。 - この時点での $ S $ を「とても長い数列」とする。 例えば $ N\ =\ 3,\ A_1\ =\ 1,\ A_2\ =\ 2,\ A_3\ =\ 3 $ なら、$ S $ は $ \{\} $ → $ \{1\} $ → $ \{1,2,1\} $ → $ \{1,2,1,3,1,2,1\} $ と変化し、「とても長い数列」は $ \{1,2,1,3,1,2,1\} $ となります。 高橋君はこの手順によって作られる「とても長い数列」に含まれる数の和を知りたがっています。これを高橋君の代わりに計算するプログラムを作成してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ ... $ A_N $ - $ 1 $ 行目には、整数 $ N\ (1\ ≦\ N\ ≦\ 30) $ が与えられる。 - $ 2 $ 行目には、$ N $ 個の整数が空白区切りで与えられる。このうち $ i\ (1\ ≦\ i\ ≦\ N) $ 番目には、整数 $ A_i\ (0\ ≦\ A_i\ ≦\ 100) $ が与えられる。 - 「とても長い数列」に含まれる数の和は $ 10^9 $ 以下となることが保証されている。

「とても長い数列」に含まれる数の和を $ 1 $ 行に出力せよ。出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 10 $ を満たすデータセットに正解した場合は、$ 60 $ 点が与えられる。 - 追加の制約のないデータセットに正解した場合は、上記とは別に $ 40 $ 点が与えられる。 ### Sample Explanation 1 この入力例は問題文中の例と同じです。 「とても長い数列」は $ \{1,2,1,3,1,2,1\} $ となり、$ 1+2+1+3+1+2+1\ =\ 11 $ であるため $ 11 $ を出力します。 ### Sample Explanation 3 「とても長い数列」はとても長くなることがあるので注意してください。