{"raw_statement":[{"iden":"problem statement","content":"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$."},{"iden":"notes","content":"*   A binary tree is a rooted tree such that each vertex has at most two direct children.\n*   A leaf in a binary tree is a vertex with zero children.\n*   The depth of a vertex $v$ in a binary tree is the distance from the tree's root to $v$. (The root has the depth of $0$.)\n*   The depth of a binary tree is the maximum depth of a vertex in the tree."},{"iden":"constraints","content":"*   $0 \\leq N \\leq 10^5$\n*   $0 \\leq A_i \\leq 10^{8}$ ($0 \\leq i \\leq N$)\n*   $A_N \\geq 1$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_0$ $A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"3\n0 1 1 2"},{"iden":"sample output 1","content":"7\n\nBelow is the tree with the maximum possible number of vertices. It has seven vertices, so we should print $7$.\n\n![image](https://img.atcoder.jp/nomura2020/0d8d99d13df036f23b0c9fcec52b842b.png)"},{"iden":"sample input 2","content":"4\n0 0 1 0 2"},{"iden":"sample output 2","content":"10"},{"iden":"sample input 3","content":"2\n0 3 1"},{"iden":"sample output 3","content":"\\-1"},{"iden":"sample input 4","content":"1\n1 1"},{"iden":"sample output 4","content":"\\-1"},{"iden":"sample input 5","content":"10\n0 0 1 1 2 3 5 8 13 21 34"},{"iden":"sample output 5","content":"264"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}