Problem Description

Takahashi has prepared a sequence $A = \{A_1, A_2, ..., A_N\}$ of length $ N $. Takahashi is trying to create a "very long sequence" based on sequence $ A $ using the following procedure:

• First, prepare a sequence of length $ 0 $ and call it $ S $.
• Concatenate $ S $, $ A_1 $, and $ S $ in this order to form a new $ S $.
• Concatenate $ S $, $ A_2 $, and $ S $ in this order to form a new $ S $.
• (Omitted)
• Concatenate $ S $, $ A_N $, and $ S $ in this order to form a new $ S $.
• The $ S $ at this point is the "very long sequence".

For example, if $ N = 3, A_1 = 1, A_2 = 2, A_3 = 3 $, then $ S $ changes as $\{\}$ → $\{1\}$ → $\{1,2,1\}$ → $\{1,2,1,3,1,2,1\}$, and the "very long sequence" becomes $\{1,2,1,3,1,2,1\}$.

Takahashi wants to know the sum of the numbers included in this "very long sequence". Create a program to calculate this on behalf of Takahashi.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ ... $ A_N $

• The first line contains an integer $N\ (1 ≦ N ≦ 30)$.
• The second line contains $ N $ integers separated by spaces. The $i\ (1 ≦ i ≦ N)$ -th of these is an integer $A_i\ (0 ≦ A_i ≦ 100)$.
• It is guaranteed that the sum of the numbers in the "very long sequence" is less than or equal to $ 10^9 $.

Output Format

Output the sum of the numbers included in the "very long sequence" on one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

11

Sample Input #2

8
0 1 3 6 12 25 50 100

Sample Output #2

652

Sample Input #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

Sample Output #3

536870912

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve the dataset where $ N ≦ 10 $, you will be awarded $ 60 $ points.
• If you correctly solve the dataset without additional constraints, you will be awarded an additional $ 40 $ points.

Sample Explanation 1

This input example is the same as the one in the problem statement. The "very long sequence" is $\{1,2,1,3,1,2,1\}$, and since $ 1+2+1+3+1+2+1 = 11 $, output $ 11 $.

Sample Explanation 3

Be aware that the "very long sequence" can become very long.

见题面 Input 部分

见题面 Output 部分