Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Game with Coins

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTwo 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.

Input

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.

Output

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.

Examples

Input

1

1

Output

-1

Input

3

1 2 3

Output

3

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2018 01:03:59 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|