Given is an integer sequence of length N+1: A_0, A_1, A_2, \ldots, A_N. Is there a binary tree of depth N such that, for each d = 0, 1, \ldots, N, there are exactly A_d leaves at depth d? If such a tree exists, print the maximum possible number of vertices in such a tree; otherwise, print -1.

Constraints

* 0 \leq N \leq 10^5
* 0 \leq A_i \leq 10^{8} (0 \leq i \leq N)
* A_N \geq 1
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_0 A_1 A_2 \cdots A_N


Output

Print the answer as an integer.

Examples

Input

3
0 1 1 2


Output

7


Input

4
0 0 1 0 2


Output

10


Input

2
0 3 1


Output

-1


Input

1
1 1


Output

-1


Input

10
0 0 1 1 2 3 5 8 13 21 34


Output

264
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    private static Scanner sc;

    public static void main(final String[] args) {
        final Main instance = new Main();
        sc = instance.new Scanner();
        instance.solve();
    }

    private class Scanner {
        String[] s;
        int i;
        BufferedReader br;
        String regex = " ";

        public Scanner() {
            s = new String[0];
            i = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        @Override
        protected void finalize() throws Throwable {
            try {
                super.finalize();
            } finally {
                destruction();
            }
        }

        private void destruction() throws IOException {
            if (br != null)
                br.close();
        }

        public String next() throws IOException {
            if (i < s.length)
                return s[i++];
            String st = br.readLine();
            while (st == "")
                st = br.readLine();
            s = st.split(regex, 0);
            i = 0;
            return s[i++];
        }

        public int nextInt() throws NumberFormatException, IOException {
            return Integer.parseInt(next());
        }

        public Long nextLong() throws NumberFormatException, IOException {
            return Long.parseLong(next());
        }

        public Double nextDouble() throws NumberFormatException, IOException {
            return Double.parseDouble(next());
        }
    }

    private void solve() {
        try {
            long n;
            long a;
            long no_leaf = 2;
            long node = 0;
            boolean isError = false;
            n = sc.nextInt();
            a = sc.nextInt();
            if (n >= 1 && a==0) {
                ArrayList<Long> list = new ArrayList<>();
                long sum = 0;
                try {
                    while (true) {
                        list.add(sc.nextLong());
                    }
                } catch (final Exception e) {

                }
                for (int i = 0; i < list.size(); i++) {
                    sum += list.get(i);
                }
                node++;
                if(no_leaf>sum) no_leaf=sum;
                if (list.get(list.size() - 1) == 0) {
                    isError=true;
                } else {
                    for (int i = 0; i < n; i++) {
                        a = list.get(i);
                        no_leaf -= a;
                        sum -= a;
                        if (no_leaf < 0) {
                            isError = true;
                            break;
                        }

                        if (no_leaf * 2 >= sum) {
                            node += a + no_leaf;
                            no_leaf = sum;

                        } else {
                            node += a + no_leaf;
                            no_leaf *= 2;
                        }
                    }
                }
                if (isError) {
                    System.out.println("-1");
                } else {
                    System.out.println(node);
                }

            } else {
                if (n==0 && a==1)
                    System.out.println("1");
                else
                    System.out.println("-1");
            }
        } catch (

        final Exception e) {
            e.printStackTrace();
        }
    }
}