Alice 和 Bob 想要玩 Nim 游戏。嗯，某种变体。

最初，他们有 $n$ 堆石子，第 $i$ 堆包含 $a_i$ 个石子。玩家轮流进行操作，Alice 先手。在每一轮中，玩家选择任意一堆至少有两个石子的堆，并将其拆分为两个新的堆，且每个新堆至少包含一个石子。之后，玩家将其中一个新堆的所有石子染成白色，将另一个新堆的所有石子染成黑色。游戏直到每一堆只剩下一个石子时结束。

游戏结束后，Alice 的得分是棋盘上白色石子的数量，Bob 的得分是黑色石子的数量。双方都希望最大化自己的得分并采取最优策略。Alice 的得分会是多少？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 128$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 128$)。 注意，石子的初始颜色无关紧要。

输出格式

输出一个整数：双方采取最优策略时 Alice 的得分。

样例

输入格式 1

2
2 2

输出格式 1

2

说明

在样例中，无论玩家如何移动，两堆石子最终都会被平分给他们。