Om Nom is the main character of a game "Cut the Rope". He is a bright little monster who likes visiting friends living at the other side of the park. However the dark old parks can scare even somebody as fearless as Om Nom, so he asks you to help him.

<image>

The park consists of 2n + 1 - 1 squares connected by roads so that the scheme of the park is a full binary tree of depth n. More formally, the entrance to the park is located at the square 1. The exits out of the park are located at squares 2n, 2n + 1, ..., 2n + 1 - 1 and these exits lead straight to the Om Nom friends' houses. From each square i (2 ≤ i < 2n + 1) there is a road to the square <image>. Thus, it is possible to go from the park entrance to each of the exits by walking along exactly n roads. 

<image> To light the path roads in the evening, the park keeper installed street lights along each road. The road that leads from square i to square <image> has ai lights.

Om Nom loves counting lights on the way to his friend. Om Nom is afraid of spiders who live in the park, so he doesn't like to walk along roads that are not enough lit. What he wants is that the way to any of his friends should have in total the same number of lights. That will make him feel safe. 

He asked you to help him install additional lights. Determine what minimum number of lights it is needed to additionally place on the park roads so that a path from the entrance to any exit of the park contains the same number of street lights. You may add an arbitrary number of street lights to each of the roads.

Input

The first line contains integer n (1 ≤ n ≤ 10) — the number of roads on the path from the entrance to any exit.

The next line contains 2n + 1 - 2 numbers a2, a3, ... a2n + 1 - 1 — the initial numbers of street lights on each road of the park. Here ai is the number of street lights on the road between squares i and <image>. All numbers ai are positive integers, not exceeding 100.

Output

Print the minimum number of street lights that we should add to the roads of the park to make Om Nom feel safe.

Examples

Input

2
1 2 3 4 5 6


Output

5

Note

Picture for the sample test. Green color denotes the additional street lights.

<image>
import java.io.*;
import java.util.*;

public class Solution {

//	public static final double EPS = 1e-9;
//	public static final int MOD = 1000000009;
//	public static final double PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679;
//	public static final int DX[] = {1, -1, 0, 0};
//	public static final int DY[] = {0, 0, 1, -1};
//	public static final int sievesize = (int) (1e6);
//	public static boolean[] prime;

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {

		public void solve(int testNumber, InputReader in, OutputWriter out) throws IOException {
			int n = in.nextInt();
			int[] arr = new int[(int) Math.pow(2, n + 1)];
			for (int i = 2; i < arr.length; i++) arr[i] = in.nextInt();
			int i = (int) (Math.pow(2, n + 1) - 1);
			long ans = 0;
			while(i > 1) {
				ans += Math.abs(arr[i] - arr[i - 1]);
				if (arr[i - 1] < arr[i]) arr[i - 1] += (arr[i] - arr[i - 1]);
				else arr[i] += (arr[i - 1] - arr[i]);
				arr[i / 2] += arr[i];
				i -= 2;
			}
			out.println(ans, "\n");
		}
		
//		static class DSU {
//			int[] par, size;
//			
//			public DSU(int n) {
//				par = new int[n];
//				size = new int[n];
//				init(n);
//			}
//			
//			public void init(int n) {
//				for (int i = 0; i < n; i++) {
//					par[i] = i;
//					size[i] = 1;
//				}
//			}
//			
//			public int find(int x) {
//				if (par[x] != x) return par[x] = find(par[x]);
//				return par[x];
//			}
//			
//			public boolean same(int x, int y) {
//				return find(x) == find(y);
//			}
//			
//			public void union(int x, int y) {
//				x = find(x);
//				y = find(y);
//				if (x == y) return;
//				par[x] = y;
//				size[y] += size[x];
//			}
//			
//			public int getSize(int x) {
//				return size[find(x)];
//			}
//		}

//		static class Node {
//			String name;
//			LinkedList<Node> list;
//			
//			public Node(String name) {
//				this.name = name;
//				list = new LinkedList<>();
//			}
//		}
        
//		static class Pair<T1, T2> {   	
//	      	T1 first;
//	      	T2 second;
//		        	
//		    public Pair(T1 first, T2 second) {
//	    		this.first = first;
//				this.second = second;
//			}
//	    }
		
//		public void sieve() {
//			prime = new boolean[sievesize + 1];
//			Arrays.fill(prime, true);
//		    for(int x = 2; x * x < sievesize; x++) { 
//		    	if(prime[x])
//		    		for(int y = x * 2; y < sievesize; y += x) 
//		    			prime[y] = false; 
//		    }
//		} 

//		public int[] shuffle(int arr[], Random gen) {
//			for (int i = arr.length - 1; i > 0; i--) {
//	            int index = gen.nextInt(i + 1);
//	            int temp = arr[index];
//	            arr[index] = arr[i];
//	            arr[i] = temp;
//			}
//			return arr;
//		}
	
//		public boolean triangle(long a, long b, long c) {
//		    return ((a+b) > c && (b+c) >a && (a+c) > b);
//		}
	
//		public boolean isPerfectSquare(long n) {
//			if (n < 0) return false;
//		    long test = (long) (Math.sqrt(n) + 0.5);
//		    return test*test == n;
//		}
	
//		public int isnum(char s) {
//			if(s=='1' || s=='2' || s=='3' || s=='4' || s=='5' || s=='6' || s=='7' || s=='8' || s=='9' || s=='0')  return 1; 
//			return 0;
//		}
	
//		public long nextPowerOf2(long n) {
//		    n--;
//		    n |= n >> 1;
//		    n |= n >> 2;
//		    n |= n >> 4;
//		    n |= n >> 8;
//		    n |= n >> 16;
//		    n++;
//		    return n;
//		}
	
//		public int gcd(int a, int b) {
//		    int t; 
//		    while (b > 0){ 
//		    	a = a % b; 
//		    	t = a; 
//		    	a = b; 
//		    	b = t; 
//		    }
//		    return a;
//		}
		
//		public int lcm(int x, int y) {
//			int a = Math.max(x, y);
//			while (true) {
//				if (a % x == 0 && a % y == 0) return a;
//				a++;
//			}
//		}
	
//		public static int findGcdArray(int[] arr) {
//			int min = Integer.MAX_VALUE;
//			for (int i = 0; i < arr.length; i++)
//				min = Math.min(min, arr[i]);
//			while (min > 1) {
//				int i = 0, s = 0;
//				while (i < arr.length) {
//					s += arr[i] % min;
//					i++;
//				}
//				if (s == 0) return min;
//				min--;
//			}
//			return 1;
//		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		
		private void tokenize() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}

		public String next() {
			tokenize();
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public char nextChar() {
			return next().charAt(0);
		}
		
		public float nextFloat() {
			return Float.parseFloat(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int size) {
			tokenize();
			int[] arr=new int[size];
			for(int i = 0; i < size; i++) {
				tokenize();
				arr[i] = Integer.parseInt(tokenizer.nextToken());
			}
			return arr;
		}
		
		public long[] nextLongArray(int size) {
			tokenize();
			long[] arr=new long[size];
			for(int i = 0; i < size; i++) {
				tokenize();
				arr[i] = Long.parseLong(tokenizer.nextToken());
			}
			return arr;
		}
		
		public float[] nextFloatArray(int size) {
			tokenize();
			float[] arr=new float[size];
			for(int i = 0; i < size; i++) {
				tokenize();
				arr[i] = Float.parseFloat(tokenizer.nextToken());
			}
			return arr;
		}

		public double[] nextDoubleArray(int size) {
			tokenize();
			double[] arr=new double[size];
			for(int i = 0; i < size; i++) {
				tokenize();
				arr[i] = Double.parseDouble(tokenizer.nextToken());
			}
			return arr;
		}

		public String[] nextStringArray(int size) throws IOException {
			String[] arr=new String[size];
			for(int i = 0; i < size; i++) 
				arr[i] = reader.readLine();
			return arr;
		}

		public char[] nextCharArray(int size) throws IOException {
			return reader.readLine().toCharArray();
		}
	}

	static class OutputWriter {
		public PrintWriter pw;

		public OutputWriter(OutputStream stream) {
			pw = new PrintWriter(stream);
		}
		
		public void println(Object... obj) {
			if (obj.length == 0) pw.println();
			else {
				String delimiter = (String) obj[obj.length - 1];
				for (int i = 0 ; i < obj.length - 2; i++) {
					pw.print(obj[i]);
					pw.print(delimiter);
				}
				pw.println(obj[obj.length - 2]);
			}
		}

		public void close() {
			pw.close();
		}

		public void flush() {
			pw.flush();
		}

		public void printStringArray(String[] arr) {
			for(int i = 0; i < arr.length; i++)
				pw.println(arr[i]);
		}
		
		public void printBooleanArray(boolean[] arr, int a , int b) {
			for(int i = a; i < b; i++)
				pw.print(arr[i] + " ");
		}

		public void printIntArray(int[] arr, int a , int b) {
			for(int i = a; i < b; i++)
				pw.print(arr[i] + " ");
		}

		public void printLongArray(long[] arr, int a , int b) {
			for(int i = a; i < b; i++)
				pw.print(arr[i] + " ");
		}

		public void printCharArray(char[] arr, int a , int b) {
			for(int i = a; i < b; i++)
				pw.print(arr[i] + " ");
		}

		public void printFloatArray(float[] arr, int a , int b) {
			for(int i = a; i < b; i++)
				pw.print(arr[i] + " ");
		}

		public void printDoubleArray(double[] arr, int a , int b) {
			for(int i = a; i < b; i++)
				pw.print(arr[i] + " ");
		}
		
		public void printIntArrayList(ArrayList<Integer> arr, int a , int b) {
			for(int i = a; i < b; i++)
				pw.print(arr.get(i) + " ");
		}
		
		public void printLongArrayList(ArrayList<Long> arr, int a , int b) {
			for(int i = a; i < b; i++)
				pw.print(arr.get(i) + " ");
		}
	}
}