CF245C.Game with Coins

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.

两名海盗波利卡普斯和瓦西里正在玩一个非常有趣的游戏。他们有 $n$ 个装有硬币的宝箱，宝箱编号为 $1$ 到 $n$ 的整数。编号为 $i$ 的宝箱中有 $a_i$ 枚硬币。

波利卡普斯和瓦西里轮流进行操作，波利卡普斯先手。每次操作中，玩家可以选择一个正整数 $x$（满足 $2\cdot x + 1 \leq n$），并从编号为 $x$、$2\cdot x$ 和 $2\cdot x + 1$ 的宝箱中各取走一枚硬币。若某个宝箱中已无硬币，则该宝箱不取硬币。当所有宝箱均为空时，游戏结束。

波利卡普斯既不是贪婪的守财奴，也不是懒惰的懒汉。因此，他想知道游戏最少需要多少步才能结束。请帮助波利卡普斯，求出游戏能够结束的最少操作步数。注意：波利卡普斯统计的是总步数（即包括他自己的操作步数和瓦西里的操作步数）。

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.

第一行包含一个整数 $n$（$1 \leq n \leq 100$）—— 表示装有硬币的宝箱数量。
第二行包含一个由空格分隔的整数序列：$a_1,\ a_2,\ \dots,\ a_n$（$1 \leq a_i \leq 1000$），其中 $a_i$ 表示游戏开始时第 $i$ 个宝箱中的硬币数量。

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。

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.

在第一个测试用例中，不存在任何可以执行的操作。因此，玩家无法清空宝箱。

在第二个样例中，仅存在一种可能的操作：$x = 1$。该操作至少需重复执行 3 次，才能清空第三个宝箱。