问题描述

高桥君准备了一个长度为 $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$。

输出

输出"非常长的数列"中数的总和，结尾处换行。

部分分

此问题设置了部分分。

• 如果满足 $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$。

输入示例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

请注意，"非常长的数列"可能会非常长。