说明

时间限制：1 Sec 内存限制：256 MB 输入文件：rpg.in 输出文件：rpg.out

你正在玩一款培育多名机器人的角色扮演游戏。

目前你拥有 $N$ 个机器人，它们的经验值分别为 $( x_1, x_2, \dots, x_N )$。

你打算通过合成系统，将这 $N$ 个机器人合并为 $1$ 个。

合成系统的详细规则如下：

- 设素材机器人的经验值为 $a$，被合成机器人的经验值为 $b$；

- 合成后，被合成机器人的经验值会增加「素材机器人经验值的一半（向下取整）」；

- 即合成后的经验值为 $( b + \lfloor \frac{a}{2} \rfloor )$ $( \lfloor \cdot \rfloor )$ 表示向下取整）；

- 素材机器人会消失。

你的目标是让最终剩下的那个机器人的经验值尽可能大，请计算这个最大可能的经验值。

输入格式

第一行：整数 $N$ 表示你拥有的机器人数量；

第二行：$N$ 个整数 $( x_1, x_2, \dots, x_N )$ 表示每个机器人的经验值，以空格分隔。

输出格式

输出一个整数，表示最终剩下的机器人能达到的最大经验值。

样例

样例 1

3
1 2 3

4

样例说明：

此时，按照以下合成步骤进行合并，最终会剩下经验值为 $4$ 的机器人：

1. 将机器人 $2$ 合成到机器人 $1$ 上：机器人 $1$ 的经验值变为 $2$，机器人 $2$ 消失；剩余机器人的经验值状态为 $[2, x, 3]$（其中 $x$ 表示该位置的机器人已消失）；

2. 将机器人 $1$ 合成到机器人 $3$ 上：机器人 $3$ 的经验值变为 $4$，机器人 $1$ 消失；剩余机器人的经验值状态为 $[x, x, 4]$，合成操作至此结束。

样例 2

5
2 2 2 2 2

6

样例说明：

此时，通过重复执行“将机器人 ( i(i>1) ) 合成到机器人 $1$ 上”的操作，最终会剩下经验值为 $6$ 的机器人，这就是最大可能值。

样例 3

16
5 48 74 84 94 13 24 15 92 79 74 89 32 30 5 24

435

数据范围

对于 16% 的数据，$N \le 5$。

对于 40% 的数据，$N \le 5000$。

对于 100% 的数据，$( 2 \leq N \leq 10^5 )$，$( 1 \leq x_i \leq 10^4 )$。