問題文

高橋君は長さ $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$ 点が与えられる。

入力例1

3
1 2 3

出力例1

11

この入力例は問題文中の例と同じです。

「とても長い数列」は $\\{1,2,1,3,1,2,1\\}$ となり、$1+2+1+3+1+2+1 = 11$ であるため $11$ を出力します。

入力例2

8
0 1 3 6 12 25 50 100

出力例2

652

入力例3

30
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例3

536870912

「とても長い数列」はとても長くなることがあるので注意してください。