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.


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

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
a = [0] + list(map(int, input().split()))
if len(a) < 3 or n % 2 == 0:
	print(-1)
else:
	ans = 0
	for x in range(n // 2, 0, -1):
		d = max(0, a[2 * x], a[2 * x + 1])
		ans += d
		a[x] -= d
	print(ans + max(0, a[1]))


n = int(input())
if n == 1 or n & 1 == 0:
	print(-1)
else:
	t = list(map(int, input().split()))
	(s, k) = (0, n // 2 - 1)
	for i in range(n - 1, 1, -2):
		p = max(t[i], t[i - 1])
		t[k] = max(0, t[k] - p)
		s += p
		k -= 1
	print(s + t[0])


t = int(input())
line = input()
lis = line.split()
lis = [int(i) for i in lis]
if t == 1 or t % 2 == 0:
	print('-1')
	quit()
count = 0
i = t
while i >= 4:
	if i % 2 == 1:
		p = i - 1
		q = int(p / 2)
		count = count + lis[i - 1]
		lis[p - 1] = lis[p - 1] - lis[i - 1]
		if lis[p - 1] < 0:
			lis[p - 1] = 0
		lis[q - 1] = lis[q - 1] - lis[i - 1]
		if lis[q - 1] < 0:
			lis[q - 1] = 0
		lis[i - 1] = 0
	else:
		p = i + 1
		q = int(i / 2)
		count = count + lis[i - 1]
		lis[p - 1] = lis[p - 1] - lis[i - 1]
		if lis[p - 1] < 0:
			lis[p - 1] = 0
		lis[q - 1] = lis[q - 1] - lis[i - 1]
		if lis[q - 1] < 0:
			lis[q - 1] = 0
		lis[i - 1] = 0
	i = i - 1
m = max(lis[0], lis[1], lis[2])
count = count + m
print(count)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	n = ii()
	a = li()
	if n == 1 or n % 2 == 0:
		print('-1')
		return
	cnt = 0
	for i in range(n // 2 - 1, -1, -1):
		x = max(a[2 * i + 1], a[2 * i + 2])
		cnt += x
		a[i] = max(0, a[i] - x)
	print(cnt + a[0])
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


import math
a_sum = 0
n = int(input())
a = [0] + [int(i) for i in input().split()]
if n % 2 == 0 or n == 1:
	print(-1)
	exit()
else:
	i = n
	while i > 3:
		if a[i] >= a[i - 1]:
			if a[i] > 0:
				a_sum += a[i]
				a[(i - 1) // 2] = a[(i - 1) // 2] - a[i]
		elif a[i - 1] > 0:
			a_sum += a[i - 1]
			a[(i - 1) // 2] = a[(i - 1) // 2] - a[i - 1]
		a[n] = 0
		a[n - 1] = 0
		i -= 1
		i -= 1
	a_max = a[3]
	if a[2] > a[3]:
		a_max = a[2]
	if a[1] > a_max:
		a_max = a[1]
	if a_max > 0:
		a_sum += a_max
	print(a_sum)
	exit()


n = int(input())
if n == 1 or n % 2 == 0:
	print(-1)
	exit()
A = [0] * (n + 1)
A[1:n + 1] = list(map(int, input().split()))
ans = 0
for i in range(n, 0, -1):
	if A[i] <= 0:
		continue
	x = int(i / 2)
	A[x] -= A[i]
	ans += A[i]
	if i % 2 == 1:
		A[i - 1] -= A[i]
	A[i] = 0
print(ans)


n = int(input())
if n == 1 or n % 2 == 0:
	print(-1)
	return
a = list(map(int, input().split(' ')))
a = [0] + a
ans = 0
for j in range(n, 0, -1):
	if j % 2 == 1:
		i = (j - 1) // 2
		ans += a[2 * i + 1]
		mina = min(a[i], a[2 * i], a[2 * i + 1])
		(a[i], a[2 * i], a[2 * i + 1]) = (a[i] - mina, a[2 * i] - mina, a[2 * i + 1] - mina)
		if a[2 * i + 1] > 0:
			nonzero = 0
			if a[i] > 0:
				a[i] = max(0, a[i] - a[2 * i + 1])
			else:
				a[2 * i] = max(0, a[2 * i] - a[2 * i + 1])
			a[2 * i + 1] = 0
	else:
		i = j // 2
		if 2 * i + 1 > n:
			print(-1)
			return
		ans += a[2 * i]
		mina = min(a[i], a[2 * i], a[2 * i + 1])
		(a[i], a[2 * i], a[2 * i + 1]) = (a[i] - mina, a[2 * i] - mina, a[2 * i + 1] - mina)
		if a[2 * i] > 0:
			a[i] = max(0, a[i] - a[2 * i])
			a[2 * i] = 0
if any(a):
	print(-1)
else:
	print(ans)


n = int(input())
A = [int(i) for i in input().split()]
if n == 1 or n % 2 == 0:
	print(-1)
	exit()
ans = 0
for i in range(n - 1, 3, -2):
	diff = max(A[i], A[i - 1])
	ans += diff
	A[(i - 1) // 2] -= diff
	A[(i - 1) // 2] = max(0, A[(i - 1) // 2])
ans += max(A[:3])
print(ans)


(n, s) = (int(input()), 0)
a = [0] + list(map(int, input().split()))
if n % 2 == 0 or n == 1:
	print(-1)
else:
	for i in range(n, 1, -2):
		mx = max(a[i], a[i - 1])
		s += mx
		a[i // 2] = max(0, a[i // 2] - mx)
	print(s + a[1])