两个海盗波利卡普斯和瓦西里玩着一个非常有趣的游戏。他们有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 次以清空第三个箱子。