Problem F
Double Up
A Double Up game consists of a sequence of $n$ numbers $a_1, \ldots , a_ n$, where each $a_ i$ is a power of two. In one move one can either remove one of the numbers, or merge two identical adjacent numbers into a single number of twice the value. For example, for sequence $4,2,2,1,8$, we can merge the $2$s and obtain $4,4,1,8$, then merge the $4$s and obtain $8,1,8$, then remove the $1$, and, finally, merge the $8$s, obtaining a single final number, $16$. We play the game until a single number remains. What is the largest number we can obtain?
Input
The input consists of two lines. The first line contains $n$ ($1 \leq n \leq 1000$). The second line contains numbers $a_1, \ldots , a_ n$, where $1\leq a_ i\leq 2^{100}$ for each $i$.
Output
The ouput consists of a single line containing the largest number that can be obtained from the input sequence $a_1, \ldots , a_ n$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 4 2 2 1 8 |
16 |
