C - Folia /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

長さ N + 1 の整数列 A_0, A_1, A_2, \ldots, A_N が与えられます。深さ N の二分木であって、d = 0, 1, \ldots, N に対して深さ d の葉の個数がちょうど A_d であるものは存在するでしょうか?存在する場合はそのような二分木の頂点数の最大値を、存在しない場合は -1 を出力してください。

注釈

  • 二分木とは、根付き木であって、それぞれの頂点の (直接の) 子の個数が 2 以下であるものを指す。
  • 根付き木の葉とは、子の個数が 0 である頂点を指す。
  • 根付き木の頂点 v の深さとは、根付き木の根から v までの距離を指す。(根の深さは 0 である。)
  • 根付き木の深さとは、根付き木の頂点の深さの最大値を指す。

制約

  • 0 \leq N \leq 10^5
  • 0 \leq A_i \leq 10^{8} (0 \leq i \leq N)
  • A_N \geq 1
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N
A_0 A_1 A_2 \cdots A_N

出力

答えを整数で出力せよ。


入力例 1

3
0 1 1 2

出力例 1

7

以下の二分木が最善です。この二分木の頂点数は 7 であるため、7 を出力します。

0d8d99d13df036f23b0c9fcec52b842b.png


入力例 2

4
0 0 1 0 2

出力例 2

10

入力例 3

2
0 3 1

出力例 3

-1

入力例 4

1
1 1

出力例 4

-1

入力例 5

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

出力例 5

264

Score : 600 points

Problem Statement

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.

Notes

  • A binary tree is a rooted tree such that each vertex has at most two direct children.
  • A leaf in a binary tree is a vertex with zero children.
  • 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.)
  • The depth of a binary tree is the maximum depth of a vertex in the tree.

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.


Sample Input 1

3
0 1 1 2

Sample Output 1

7

Below is the tree with the maximum possible number of vertices. It has seven vertices, so we should print 7.

0d8d99d13df036f23b0c9fcec52b842b.png


Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

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

Sample Output 5

264