B - とても長い数列 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は長さ 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

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