P12740 [POI 2016 R2] 不是 Nim 游戏 Not Nim

翻译来自于 [LibreOJ](https://loj.ac/p/5036)。

**题目译自 [XXIII Olimpiada Informatyczna — II etap](https://sio2.mimuw.edu.pl/c/oi23-2/dashboard/) [Wcale nie Nim](https://szkopul.edu.pl/problemset/problem/M5CruI5eCu8elnNFHuiXBrvV/statement/)** 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$，表示每对堆的初始石头数量。

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

**样例 1 解释** 最优游戏过程可能如下： $$ 1122 \rightarrow 1120 \rightarrow 1111 \rightarrow 1110 \rightarrow 1101 \rightarrow 1100 \rightarrow 2000 \rightarrow 0000 $$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $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$。