题目描述

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

输入格式

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

$N$ $A_0$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

答えを整数で出力せよ。

题目大意

题目描述

问题网址

给定一个长度为 $N+1$ 的非负整数序列 $A_0,A_1,A_2,\cdots,A_N$。问是否存在一棵深度为 $N$ 的二叉树，对于每一个 $d=0,1,2,\cdots,N$，使得在深度 $d$ 处正好有 $A_d$ 个叶子结点。如果存在，则输出此类二叉树的最大顶点数量，如果不存在，则输出 $-1$。

输入格式

输入格式如下：

$N$
$A_0$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

$1$ 行 $1$ 个整数，代表答案。

说明/提示

注释

• 二叉树是一棵有根树，每个结点最多有两个子结点。
• 二叉树中的叶子是没有子结点的结点。
• 二叉树中结点 $v$ 的深度是从根结点到 $v$ 的距离（根结点的深度为 $0$）。
• 二叉树的深度是树中结点的最大深度。

数据范围

• $0\le N\le 10^5$
• $0\leq A_i\le 10^8$（$0\le i\le N$）
• $A_N\ge 1$
• 所有输入均为非负整数。

示例说明 1

对于样例 $1$，以下是一种可能的答案：

翻译

3
0 1 1 2

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

提示

注釈

• 二分木とは、根付き木であって、それぞれの頂点の (直接の) 子の個数が $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$
• 入力はすべて整数である

Sample Explanation 1

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