Bythony 和他的弟弟 Bytie 经常玩 Nim 游戏。Bythony 向弟弟解释了 Nim 游戏的必胜策略，但 Bytie 似乎无法掌握，因为他输得很频繁。因此，小 Bytie 不断提出一些替代规则，希望这些规则能让游戏变得简单一些。

他最新的提议如下：有 $n$ 对堆，其中第 $i$ 对中的每一堆最初都有 $a_i$ 个石子。玩家轮流行动。Bytie 的每次移动包括从他选择的某一堆中移除任意数量的正整数个石子。而 Bythony 的每次移动包括在他选择的一对堆中移动任意数量的正整数个石子（即从其中一堆移到另一堆）。Bytie 先手。无法进行移动的玩家输掉游戏。

Bythony 很快意识到他无法赢得这场游戏，但他还是同意陪弟弟玩，以让弟弟开心。事实上，他打算尽可能地拖延不可避免的失败，即在输掉游戏之前尽可能多地进行移动。请编写一个程序，计算当双方都采取最优策略时，游戏的持续时间（即总移动次数）。其中 Bytie 的目标是以最少的步数获胜，而 Bythony 的目标是在输掉游戏前尽可能多地进行移动。

输入格式

第一行包含一个正整数 $n$，表示堆的对数。 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，由空格分隔，表示每一对中两堆石子的初始数量。

输出格式

输出一行，包含一个整数：当双方都采取最优策略时，游戏结束时的总移动次数。

样例

样例输入 1

2
1 2

样例输出 1

7

说明

样例的一种最优移动序列如下： $1\ 1\ 2\ 2 \to 1\ 1\ 2\ 0 \to 1\ 1\ 1\ 1 \to 1\ 1\ 1\ 0 \to 1\ 1\ 0\ 1 \to 1\ 1\ 0\ 0 \to 2\ 0\ 0\ 0 \to 0\ 0\ 0\ 0$

子任务

测试集由以下子任务组成。在每个子任务中，可能包含多个测试组。所有子任务均满足条件 $a_i \le 1\,000\,000\,000$。