Game with Coins

题意翻译

#### 题目描述 两个海盗 Polycarpus 和 Vasily 玩了一个非常有趣的游戏。他们有 $n$ 个装有硬币的箱子，这些箱子都有一个从 $1$ 到 $n$ 的整数编号。编号为 $i$ 的箱子有 $a_{i}$ 个硬币。 Polycarpus 和 Vasily 轮流出手。 Polycarpus 首先出手。在移动过程中，玩家可以选择一个正整数 $x$ $(2×x+1 \leq n)$ 并从每个编号为 $x$ 、 $2 \times x$ 、$2 \times x+1$ 的箱子中取出一个硬币。 可能会发现某些箱子没有硬币，在这种情况下，不会从这个箱子中取出硬币。当所有箱子都没有硬币时，游戏结束。 Polycarpys 非常懒，但是他又想知道游戏最少可以玩几轮，于是他把这个任务交给了你。 #### 输入格式 第一行一个整数 $n$ ，表示箱子的个数；\ 第二行 $n$ 个整数，表示每个箱子装有的硬币数。 #### 输出格式 一个整数，表示完成游戏最少需要的轮数。如果无法结束游戏，输出 `-1` 。

题目描述

Two pirates Polycarpus and Vasily play a very interesting game. They have $ n $ chests with coins, the chests are numbered with integers from 1 to $ n $ . Chest number $ i $ has $ a_{i} $ coins. Polycarpus and Vasily move in turns. Polycarpus moves first. During a move a player is allowed to choose a positive integer $ x $ $ (2·x+1<=n) $ and take a coin from each chest with numbers $ x $ , $ 2·x $ , $ 2·x+1 $ . It may turn out that some chest has no coins, in this case the player doesn't take a coin from this chest. The game finishes when all chests get emptied. Polycarpus isn't a greedy scrooge. Polycarpys is a lazy slob. So he wonders in what minimum number of moves the game can finish. Help Polycarpus, determine the minimum number of moves in which the game can finish. Note that Polycarpus counts not only his moves, he also counts Vasily's moves.

输入输出格式

输入格式

The first line contains a single integer $ n $ $ (1<=n<=100) $ — the number of chests with coins. The second line contains a sequence of space-separated integers: $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=1000) $ , where $ a_{i} $ is the number of coins in the chest number $ i $ at the beginning of the game.

输出格式

Print a single integer — the minimum number of moves needed to finish the game. If no sequence of turns leads to finishing the game, print -1.

输入输出样例

输入样例 #1

1
1

输出样例 #1

-1

输入样例 #2

3
1 2 3

输出样例 #2

3

说明

In the first test case there isn't a single move that can be made. That's why the players won't be able to empty the chests. In the second sample there is only one possible move $ x=1 $ . This move should be repeated at least 3 times to empty the third chest.