#1196. 反应[妖怪测谎仪]

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Komeiji Koishi

题目描述

给出一个长度为 的序列 。是否存在一棵二叉树,使得,对于任何一个深度 ,树上恰好有 个深度为 的点是叶子,且这棵二叉树的深度为 (根节点的深度为0),若存在,输出二叉树的最大节点数,若不存在输出"-1".

二叉树的深度定义为其中节点的最大深度.

输入格式

第一行一个正整数 .

接下来一行 个非负整数,表示 .

输出格式

一行一个整数表示答案.

样例

样例输入1

3
0 1 1 2

样例输出1

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

数据范围与提示