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 ai 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: a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai 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.
import java.util.*;
import java.io.*;
/*
99
557 852 325 459 557 350 719 719 400 228 985 674 942 322 212 553 191 58 720 262 798 884 20 275 576 971 684 340 581 175 641 552 190 277 293 928 261 504 83 950 423 211 571 159 44 428 131 273 181 555 430 437 901 376 361 989 225 399 712 935 279 975 525 631 442 558 457 904 491 598 321 396 537 555 73 415 842 162 284 847 847 139 305 150 300 664 831 894 260 747 466 563 97 907 42 340 553 471 411
 */
public class eight 
{	
	public static void main(String[] arg) throws IOException
	{
		new eight();
	}

	public eight() throws IOException
	{
		//JoltyScanner in = new JoltyScanner(System.in);
		//FastInput in = new FastInput(System.in);
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		int[] arr = new int[n+1];
		for(int i = 1; i <= n; i++)
		{
			arr[i] = in.nextInt();
		}
		HashSet<Integer> possible = new HashSet<Integer>();
		for(int i = 1; 2*i+1 <= n; i++)
		{
			possible.add(i);
			possible.add(2*i);
			possible.add(2*i+1);
		}
		int answer = 0;
		for(int i = n; i > 1; i--)
		{

			int x = (i-(i%2))/2;
			while(arr[i] > 0)
			{
				arr[x]--;
				arr[x*2]--;
				if(i%2 == 1)
					arr[x*2+1]--;
				answer++;
			}
			
		}
		if(arr[1] > 0)
			answer += arr[1];
		out.println(possible.size()==n?answer:"-1");
		in.close(); out.close();
	}
	

	class FastInput 
	{
		BufferedReader reader;
		StringTokenizer tokenizer;
		
		public FastInput(InputStream input)
		{
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}
		String next() throws IOException
		{
			while( ! tokenizer.hasMoreTokens() )
			{
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}
		char nextChar() throws IOException { return next().charAt(0); }
		int nextInt() throws IOException { return Integer.parseInt(next()); }
		double nextDouble() throws IOException { return Double.parseDouble(next()); }
		long nextLong() throws IOException { return Long.parseLong(next()); }
		void close() throws IOException { reader.close(); }
	}
	class JoltyScanner 
	{
	    public static final int BUFFER_SIZE = 1 << 16;
		public static final char NULL_CHAR = (char) -1;

	    byte[] buffer = new byte[BUFFER_SIZE];
		boolean EOF_FLAG = false;
		int bufferIdx = 0, size = 0;
		char c = NULL_CHAR;
		BufferedInputStream in;

		public JoltyScanner(InputStream in) 
		{
			this.in = new BufferedInputStream(in, BUFFER_SIZE);
		}

		public int nextInt() 
		{
			long x = nextLong();
			if (x > Integer.MAX_VALUE || x < Integer.MIN_VALUE) 
			{
				throw new ArithmeticException("Scanned value overflows integer");
			}
			return (int) x;
		}

		public long nextLong() 
		{
			boolean negative = false;
			if (c == NULL_CHAR) 
			{
				c = nextChar();
			}
			for (; !EOF_FLAG && (c < '0' || c > '9'); c = nextChar()) 
			{
				if (c == '-') 
				{
					negative = true;
				}				
			}
			checkEOF();
			long res = 0;
			for (; c >= '0' && c <= '9'; c = nextChar()) 
			{
				res = (res << 3) + (res << 1) + c - '0';
			}
			return negative ? -res : res;
		}

	    public char nextChar() 
	    {
			if (EOF_FLAG) 
			{
				return NULL_CHAR;
			}
			while (bufferIdx == size) 
			{
				try 
				{
					size = in.read(buffer);
					if (size == -1) 
					{
						throw new Exception();
					}
				} 
				catch (Exception e) 
				{
					EOF_FLAG = true;
					return NULL_CHAR;
				}
				if (size == -1) 
				{
					size = BUFFER_SIZE;
				}
				bufferIdx = 0;
			}
			return (char) buffer[bufferIdx++];
		}

	    public void checkEOF() 
	    {
			if (EOF_FLAG) 
			{
				throw new EndOfFileException();
			}
		}
	    public void close()
	    {
	    	;
	    }
		public class EndOfFileException extends RuntimeException 
		{
		}
	}
	class FastScanner 
	{
		final BufferedReader reader;
		String line;
		int index;
		public FastScanner(InputStream in)
		{
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String readLine()
		{
			try
			{
				String line = reader.readLine();
				if(line == null) throw new IOException("End of stream");
				return line;
			}
			catch(IOException exception)
			{
				throw new RuntimeException(exception);
			}
		}
		public String nextLine()
		{
			if(line==null) return readLine();
			String s = line;
			line = null;
			return s.substring(index);
		}
		public String next()
		{
			if(line == null)
			{
				line = readLine();
				index = 0;
			}
			while(index >= line.length())
			{
				line = readLine();
				index = 0;
			}
			while(Character.isWhitespace(line.charAt(index)))
			{
				index++;
				while(index >= line.length())
				{
					line = readLine();
					index = 0;
				}
			}
			int endIndex = index;
			while(endIndex < line.length() && !Character.isWhitespace(line.charAt(endIndex)))
				endIndex++;
			String s = line.substring(index, endIndex);
			index = endIndex;
			return s;
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public long nextLong() { return Long.parseLong(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public void close() {;}
	}
}
