404237: GYM101466 B Maximum Tree

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Maximum Treetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Ivan is a new professor of the University of Nice Algebra Lovers (UNAL), he is going to give a data structures course, that's why he is preparing his slides and wants to draw a beautiful rooted tree. As he loves math, he has a very special array of numbers A and he wants to use each element of the array as the number of children for some level in the tree. For example, if A = [2, 1, 3] two of the possible trees he could draw are the following:

Ivan wants to draw a rooted tree that has the maximum number of nodes. As he is busy with LaTeX he wants you to write a program that computes such number.

Input

The first line consists of an integer n (1 ≤ n ≤ 32), the next line contains n numbers separated by a single space, the elements of A (1 ≤ Ai ≤ 10).

Output

Print one number, the maximum number of nodes Ivan can draw. It is guaranteed that the answer fits on a 63-bits integer.

ExampleInput
3
2 1 3
Output
16
Note

The number of levels of the tree (except for the root) is the same as the number of elements in the array

加入题单

上一题 下一题 算法标签: