配点 : $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$

出力

答えを整数で出力せよ。

3
0 1 1 2

7

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

4
0 0 1 0 2

10

2
0 3 1

-1

1
1 1

-1

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

264