Phoebe - The Pickpocketer

0

0 votes
Medium
Problem

Phoebe being a pickpocketer was once chased by police. After a long chasing she just managed to hide inside a building. Now police has surrounded the building. Phoebe knows that after some time police will break in the building and surely she will get arrested. Being very smart she thought of a mind game, she makes a deal with police that she will surrender herself and give them all the evidence. So, she gave them an array A (of size n) of numbers and asked them to regenerate array using only n-1 turns and following certain rules.

  1. If two adjacent elements are equal then they can merge both of them with their addition.
  2. If two adjacent elements are not equal then they can merge both of them with the minimum of the two.

Phoebe is very smart at this, but police knows that you are more smarter than Phoebe. Help police finding out the maximum integer that can be generated by following these rules.

Note : At every step size of the array decreases by one element.

Input

First line contains single integer n denoting number of elements.

Second line contains n integers.

Output

Contains single maximum possible integer that can be generated by following the given rules.

Constraints

2<= n <=16

1<= A[i] <=30

Author - Nipun Garg

Tester - Nipun Garg

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  1. We will merge a[1] and a[2], array will become {2, 2 , 4}
  2. We will merge a[1] and a[2], array will become {4 , 4}
  3. We will merge a[1] and a[2], array will become {8}, which is the final answer.
Editor Image

?