分数: 600 点
问题陈述
给定的是长度的整数序列 N+1: A_0, A_1, A_2, \ldots, A_N。是否存在深度二叉树 N 这样,对于每个 d = 0, 1, \ldots, N,正好有 A_d 离开深处 d?如果存在这样的树,则打印该树中可能的最大顶点数;否则,打印 -1.
注释
- 二叉树是有根树,每个顶点最多有两个直接子节点。
- 二叉树中的叶子是具有零个子节点的顶点。
- 顶点的深度 二叉树中的 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.
示例输入 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