← 返回题目列表

Codeforces · 245/C

C. 硬币游戏

中文机器翻译题面 查看原题

两个海盗波利卡普斯和瓦西里玩着一个非常有趣的游戏。他们有n个装有硬币的箱子,箱子用1到n的整数编号。第 i 号箱子有 ai 硬币。

波利卡普斯和瓦西里轮流移动。波利卡波斯首先行动。在移动过程中,玩家可以选择一个正整数 x (2·x + 1 ≤ n),并从每个编号为 x、2·x、2·x + 1 的箱子中取出一枚硬币。可能会发现某些箱子没有硬币,在这种情况下,玩家不会从该箱子中取出硬币。当所有宝箱都被清空时游戏结束。

波利卡帕斯不是一个贪婪的守财奴。波利卡皮斯是个懒惰的懒鬼。所以他想知道游戏最少可以完成多少步。帮助波利卡普斯确定游戏可以完成的最少步数。请注意,波利卡帕斯不仅计算他的步数,还计算瓦西里的步数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100) — 装有硬币的箱子数量。第二行包含一系列以空格分隔的整数:a1, a2, ..., an (1 ≤ ai ≤ 1000),其中 ai 是游戏开始时 i 号箱子中的硬币数量。

输出

打印一个整数——完成游戏所需的最少步数。如果没有顺序的回合可以完成游戏,则打印 -1。

示例

输入 #1

1
1

输出 #1

-1

输入 #2

3
1 2 3

输出 #2

3

注意

在第一个测试用例中,无法进行任何操作。这就是为什么玩家无法清空宝箱的原因。

在第二个示例中,只有一个可能的移动 x = 1。此移动应重复至少 3 次以清空第三个箱子。