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

제한

힌트