404237: GYM101466 B Maximum Tree

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.

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 ≤ A_i ≤ 10).

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

3
2 1 3

16

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