30529번 - 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?

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$.

The ouput consists of a single line containing the largest number that can be obtained from the input sequence $a_1, \ldots, a_n$.