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

public class Main {

    private static final boolean DEBUG = false;

    private final void solve(final InputReader in, final OutputWriter out) throws Exception {

        final int n = in.nextInt();
        int[] prev = new int[1 << (n + 2)];

        for (int i = 2; i < (1 << (n + 1)); ++i) {
            prev[i] = in.nextInt();
        }

        int result = 0;
        int max = -1;

        for (int i = (1 << n); i < (1 << (n + 1)); ++i) {
            int t = i;
            int cnt = 0;
            while (t > 1) {
                cnt += prev[t];
                t /= 2;
            }
            max = Math.max(max, cnt);
        }

        boolean[] notUp = new boolean[1 << (n + 2)];
        boolean[] used = new boolean[1 << (n + 2)];

        for (int q = (1 << n); q < (1 << (n + 1)); ++q) {

            int currentMax = -1;
            int currentIndex = -1;

            for (int i = (1 << n); i < (1 << (n + 1)); ++i) {

                if (used[i]) {
                    continue;
                }

                int t = i;
                int cnt = 0;
                while (t > 1) {
                    cnt += prev[t];
                    t >>= 1;
                }

                if (cnt > currentMax) {
                    currentMax = cnt;
                    currentIndex = i;
                }
            }

            used[currentIndex] = true;
            int add = max - currentMax;

            int t = currentIndex;
            while (t / 2 >= 1 && !notUp[t / 2]) {
                notUp[t] = true;
                t >>= 1;
            }

            prev[t] += add;
            notUp[t] = true;


            result += add;
        }

        out.writeln(result);
    }

    public static void main(String[] _args) {
        final String[] args = _args;
        Thread th = new Thread(null, new Runnable() {
            @Override
            public void run() {
                runMain(args);
            }
        }, "test", 32 << 20);
        th.setPriority(Thread.MAX_PRIORITY);
        th.start();
        try {
            th.join();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    private static final void runMain(String[] args) {
        try {

            final InputReader in;
            final OutputWriter out;

            if (DEBUG) {

                final String fileIn = Main.class.getSimpleName().toLowerCase() + ".in";
                final String fileOut = Main.class.getSimpleName().toLowerCase() + ".out";

                in = new InputReader(new FileInputStream(fileIn));
                out = new OutputWriter(new FileWriter(fileOut));
            } else {

                in = new InputReader(System.in);
                out = new OutputWriter(new OutputStreamWriter(System.out));
            }

            new Main().solve(in, out);

            out.close();

        } catch (Exception ex) {

            throw new RuntimeException(ex);
        }
    }

    private static final class InputReader {

        private static final byte ZERO = '0';
        private static final byte NINE = '9';

        private static final int BUFFER_SIZE = 32 << 20;

        private final BufferedInputStream in;

        private final byte[] buffer = new byte[BUFFER_SIZE];
        private int bufferSize = 0;
        private int offset = buffer.length;
        private final StringBuilder sb = new StringBuilder(1 << 20);

        private InputReader(final InputStream in) {
            this.in = (in instanceof BufferedInputStream) ? ((BufferedInputStream) in) : (new BufferedInputStream(in));
        }

        private final int read() throws Exception {
            if (offset >= bufferSize) {
                bufferSize = in.read(buffer);
                if (bufferSize <= 0) {
                    return -1;
                }
                offset = 0;
            }
            return buffer[offset++];
        }

        private final boolean isWhiteSpace(final int c) {
            return c == ' ' || c == '\r' || c == '\t' || c == '\n' || c == -1;
        }

        public final String next() throws Exception {
            sb.setLength(0);
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            while (!isWhiteSpace(c)) {
                sb.append((char) c);
                c = read();
            }
            return sb.toString();
        }

        public final char nextChar() throws Exception {
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            return (char) c;
        }

        public final int nextInt() throws Exception {
            int result = 0;
            boolean negative = false;
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            if (c == '-') {
                negative = true;
                c = read();
            }
            while (!isWhiteSpace(c)) {
                result = result * 10 - '0' + c;
                c = read();
            }
            return negative ? -result : result;
        }

        public final long nextLong() throws Exception {
            long result = 0;
            boolean negative = false;
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            if (c == '-') {
                negative = true;
                c = read();
            }
            while (!isWhiteSpace(c)) {
                result = result * 10 - '0' + c;
                c = read();
            }
            return negative ? -result : result;
        }
    }

    private static final class OutputWriter {

        private static final String NEW_LINE = String.format("%n");

        private final Writer output;
        private final StringBuilder buffer = new StringBuilder(32 << 20);

        public OutputWriter(final Writer output) {

            this.output = output;
        }

        public void write(final int i) {

            buffer.append(i);
        }

        public void write(final String s) {

            buffer.append(s);
        }

        public void writeln(final String s) {

            buffer.append(s);
            buffer.append(NEW_LINE);
        }

        public void writeln(final long l) {

            buffer.append(l);
            buffer.append(NEW_LINE);
        }

        public void writeln(final int i) {

            buffer.append(i);
            buffer.append(NEW_LINE);
        }

        public void close() throws Exception {

            output.write(buffer.toString());
            output.flush();
            output.close();
        }
    }
}
