Description

在纸上写下 $n$ 个数 $a_1,a_2...a_n$，然后按顺序将两两相邻的数字相加，每次相加得到的结果按顺序写在下一行，这样第二行就会得到 $n-1$ 个新数。然后对第二行执行相同操作，得到第三行，以此类推，直到最后一行只剩一个数 $s$，求 $s$ 的值。

例如：给出四个数 $7,3,5,6$，每一行的结果如下：

$7,3,5,6$

$10,8,11$

$18,19$

$37$

因此最终答案为37。

Format

Input

第一行：一个正整数 $n$，表示数据个数

第二行：$n$ 个正整数

Output

最后一行唯一的一个整数 $s$

Samples

5
3 5 1 1 1

34

6
1 1 1 1 1 1

32

Limitation

对于100%的数据，$1≤n≤25；1≤a_i<10^9$。