← 返回题目列表

AtCoder · nomura2020_c

C. 福利亚

中文机器翻译题面 查看原题

分数: 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.

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