{"problem":{"name":"Folia","description":{"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$? ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"nomura2020_c"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_0$ $A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]\n\n## Notes\n\n*   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.","is_translate":false,"language":"English"}],"meta":{"iden":"nomura2020_c","tags":[],"sample_group":[["3\n0 1 1 2","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)"],["4\n0 0 1 0 2","10"],["2\n0 3 1","\\-1"],["1\n1 1","\\-1"],["10\n0 0 1 1 2 3 5 8 13 21 34","264"]],"created_at":"2026-03-03 11:01:14"}}