题目描述

题目译自 XXIII Olimpiada Informatyczna — II etap Wcale nie Nim

Bajtoni 和他的弟弟 Bajtuś 经常玩 Nim 游戏。Bajtoni 曾向弟弟讲解过游戏的制胜策略，但 Bajtuś 总是难以掌握，常常输掉比赛。因此，他不断提出修改游戏规则的建议，希望让游戏变得更简单。

最近，Bajtuś 提出了一个新玩法：游戏有 $n$ 对堆，每对中的两个堆初始各有 $a_i$ 个石头。两位玩家轮流行动。Bajtuś 在他的回合可以从任意一个堆中取走任意非零数量的石头。而 Bajtoni 在他的回合则从某对堆中选择一个堆，取走任意非零数量的石头，并将这些石头放入该对的另一个堆中。Bajtuś 率先行动。无法行动的玩家输掉游戏。

Bajtoni 很快发现，按照这样的规则，他几乎没有胜算。但为了不让弟弟失望，他同意试玩几局。然而，他暗自下定决心，要尽可能延长游戏时间，推迟不可避免的失败。请帮助 Bajtoni 编写程序，计算在双方都采取最优策略（Bajtuś 追求最快胜利，Bajtoni 追求最长游戏时间）的情况下，游戏最多能持续多少回合。

输入格式

第一行包含一个正整数 $n$，表示堆对的数量。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每对堆的初始石头数量。

输出格式

输出一行，包含一个整数，表示在双方最优策略下，游戏结束前的总回合数。

2
1 2

7

最优游戏过程可能如下：

$$1122 \rightarrow 1120 \rightarrow 1111 \rightarrow 1110 \rightarrow 1101 \rightarrow 1100 \rightarrow 2000 \rightarrow 0000 $$

附加样例

1. $n=1, a_1=100$，结果 $15$。
2. $n=5$，所有堆各 $2$ 个石头，结果 $21$。
3. $n=3, a_1=10^7, a_2=10^8, a_3=10^9$，结果 $163$。
4. $n=3000, a_i=i$，结果 $65197$。
5. $n=100000$，所有堆各 $1$ 个石头，结果 $200001$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n=1$	$10$
$2$	$\sum a_i \leq 10$	$10$
$3$	$n \leq 3$	$20$
$4$	$n \leq 3000$	$20$
$5$	$n \leq 500000$	$40$

对于所有子任务，$a_i \leq 10^9$。