Problem:


Score : 600 points

Problem Statement

Given is an integer sequence of length N+1: A_0, A_1, A_2, \ldots, A_N. Is there a binary tree of depth N such that, for each d = 0, 1, \ldots, N, there are exactly A_d leaves at depth d? If such a tree exists, print the maximum possible number of vertices in such a tree; otherwise, print -1.

Notes

A binary tree is a rooted tree such that each vertex has at most two direct children.

A leaf in a binary tree is a vertex with zero children.

The depth of a vertex v in a binary tree is the distance from the tree's root to v. (The root has the depth of 0.)

The depth of a binary tree is the maximum depth of a vertex in the tree.

Constraints

0 \leq N \leq 10^5

0 \leq A_i \leq 10^{8} (0 \leq i \leq N)

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

Below is the tree with the maximum possible number of vertices. It has seven vertices, so we should print 7.

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

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

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0:
    print(1 if a[0]==1 else -1)
    exit()
e=[1-a[0]]
for i in range(n):
    e.append(max(e[i]-a[i],0)*2)
#print(e)
p=[i for i in a]
for i in range(n-1,-1,-1):
    if -p[i+1]//2*-1+p[i]>e[i]:
        print(-1)
        exit()
    if p[i+1]+p[i]>e[i]:
        p[i]=e[i]
    else:
        p[i]+=p[i+1]
print(sum(p))
#print(p)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
nleaf=[0 for i in range(n+1)]
nleaf[0]=1-lis[0]
if nleaf[0]<0:
    print(-1)
    sys.exit()
for i in range(n):
    nleaf[i+1]=nleaf[i]*2-lis[i+1]
    if nleaf[i+1]<0:
        print(-1)
        sys.exit()
#print(lis)
#print(nleaf)
u=list(reversed(lis))
sup=[0 for i in range(n+1)]
for i in range(n):
    sup[i+1]=min(sup[i]+u[i],nleaf[n-i-1])
    #print(sup[i]+u[i],nleaf[n-i-1])
    #print(min(sup[i]+u[i],nleaf[n-i-1]))
#print(sup)
print(sum(lis)+sum(sup))

Submission status: Accepted

Solution code:
n=int(input())
a= list(map(int, input().split()))

# 各階層で可能な点のmin、max
v=[[0,0] for i in range(n+1)]
v[n]=[a[-1],a[-1]]
for i in range(n-1,-1,-1):
    v[i][0]=-(-v[i+1][0]//2)+a[i]
    v[i][1]=v[i+1][1]+a[i]


if v[0][0]>1:
    print(-1)
    exit()

ans=1
# w＝各階層で葉をもつ頂点の個数
w=1
# 各階層でできるだけ多く点をとる。
for i in range(1,n+1):
    w=min(w*2,v[i][1])
    ans+=w
    # 葉っぱは次の階層の根にならない
    w-=a[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

if N == 0 and A[0] != 1:                            # N=0なら葉は1
    ans = -1
elif N != 0 and A[0] != 0:                          # N>0ならd=0の葉は0
    ans = -1
else:
    ans = 1                                         # 頂点合計
    node = 1                                        # 深さdの頂点
    lateFolia = sum(A)                              # 残りの葉
    preFolia = 0                                    # 深さd-1の葉

    for d in range(1, N+1):                         # d=0は初期値固定なのでd=1以降の計算
        folia = A[d]                                # 深さdの葉
        node = min((node-preFolia)*2, lateFolia)    # 深さdの頂点の上界 (以下の条件を満たすもの)
                                                    # ・深さd-1の頂点のうち葉ではないものの個数の2倍
                                                    # ・残りの葉の数 (*深さdも含む)

        if node < folia:                            # 頂点<葉はありえない
            ans = -1
            break

        ans += node                                 # 頂点合計を更新
        lateFolia -= folia                          # 残りの葉の数を更新
        preFolia = folia                            # 深さd-1の葉を記憶

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

if N == 0 and A[0] != 1:                            # N=0なら葉は1
    ans = -1
elif N != 0 and A[0] != 0:                          # N>0ならd=0の葉は0
    ans = -1
else:
    ans = 1                                         # 頂点合計
    node = 1                                        # 深さdでの頂点
    lateFolia = sum(A)                              # 残りの葉
    preFolia = 0                                    # 深さd-1の葉

    for d in range(1, N+1):                         # d=0は初期値固定なのでd=1以降の計算
        folia = A[d]                                # 深さdの葉
        node = min((node-preFolia)*2, lateFolia)    # 深さdの頂点

        if node < folia:                            # 頂点<葉はありえない
            ans = -1
            break

        ans += node                                 # 頂点合計を更新
        lateFolia -= folia                          # 残りの葉の数を更新
        preFolia = folia                            # 深さd-1の葉を記憶

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    aa = LI()

    if n == 0:
        if aa[0] == 1:
            return 1
        return -1

    if aa[0] != 0:
        return -1

    b = [1]
    c = 1
    for a in aa[1:-1]:
        if a > c * 2:
            return -1
        c = c * 2 - a
        b.append(c)

    if c * 2 < aa[-1]:
        return -1

    r = c = aa[-1]
    for a,b in list(zip(aa[:-1],b))[::-1]:
        t = (c+1) // 2
        if t > b:
            return -1
        c = a + min(b, c)
        r += c

    if c != 1:
        return -1

    return r

print(main())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

B = []

if N == 0:
    if A[0] != 1:
        print(-1)
        exit()
    else:
        print(1)
        exit()

else:
    if A[0] != 0:
        print(-1)
        exit()
    else:
        B.append(1)
        for i in range(1, N + 1):
            B.append((B[i - 1] - A[i - 1]) * 2)
            if (A[i] > B[i] or (A[i] == B[i] and i != N)):
                print(-1)
                exit()

        ans = 0
        ans += A[N]
        B[N] = A[N]
        for i in range(N - 1, -1, -1):
            ans += min(B[i], B[i + 1] + A[i])
            B[i] = min(B[i], B[i + 1] + A[i])

        print(ans)
        exit()

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
A = list(map(int, input().split()))
Acum = list(accumulate(reversed(A)))
Acum.reverse()

flexibility = 1
ans = 0
for i, a in enumerate(A):
    if flexibility < a:
        print(-1)
        exit()
    ans += min(flexibility, Acum[i])
    flexibility = 2*(flexibility-a)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0

l = [0]*(n+1)
l[-1] = a[-1]
for i in range(n-1,-1,-1):
    l[i] += l[i+1]+a[i]

if a[0] == 1:
    if n > 0:
        print(-1)
        exit()
    else:
        print(1)
        exit()
b = 1
ans = 0
for i in range(n+1):
    if b < a[i]:
        print(-1)
        exit()
    else: 
        b = min(b,l[i])
        ans += b
        b = (b-a[i])*2   
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
 
n = int(readline())
a = list(map(int,readline().split()))

b = [0]*(n+1)
b[-1] = a[-1]
for i in range(n-1,-1,-1):
  b[i] = b[i+1]+a[i]
#print(b)
c = [1]*(n+1)
for i in range(n):
  c[i+1] = (c[i]-a[i])*2
#print(c)
ans = 0
for i in range(n+1):
  m = min(b[i],c[i])
  ans += m
  
if m < 0 or a[0] != 0 or c[-1] < a[-1]:
  ans = -1

if n == 0 and a[0] == 1:
  ans = 1
  
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))  #葉の数

    s=[0]*(n+1)
    for i in range(n,-1,-1):
        if i==n:
            s[i]=a[i]
        else:
            s[i]+=a[i]+s[i+1]

    b=[0]*(n+1)  #葉でない頂点数
    res=0
    flag=True
    for i in range(n+1):
        if i==0:
            if a[i]>=2:
                flag=False
                break
            if a[i]==1: b[i]=0
            else: b[i]=1
            res+=1
        else:
            v_max=min(s[i],2*b[i-1])
            if v_max<a[i]:
                flag=False
                break
            else:
                b[i]=v_max-a[i]
                res+=v_max
    
    if flag:
        print(res)
    else:
        print(-1)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    max_at_level = [0]*(N+1)
    total_leafs = sum(A)
    large_level = math.ceil(math.log(total_leafs, 2))
    vertices_in_layer = 1
    total_vertex_count = 0
    next_level_possible_space = 1
    for level in range(N+1):
        level_possible_space = next_level_possible_space
        leafs_in_level = A[level]
        total_leafs -= leafs_in_level
        # print(f"total_leafs: {total_leafs}, leafs_in_level: {leafs_in_level}, level_possible_space: {level_possible_space}")
        level_open_space = level_possible_space - leafs_in_level
        if level_open_space < 0:
            print(-1)
            return
        additional_vertices_in_level = min(level_open_space, total_leafs)
        total_vertex_count += leafs_in_level + additional_vertices_in_level
        next_level_possible_space = min(2*level_open_space, total_leafs)

    print(total_vertex_count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
k = 1-a[0]
s -= a[0]
ans = 1

for i in range(1,n+1):
  if k*2 <= s:
    k *= 2
  else:
    k = s
  ans += k
  k -= a[i]
  s -= a[i]

if k == 0 and s == 0:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
from math import *

if __name__ == '__main__':
    N = int(input())
    s = input().rstrip().split(' ')
    A = [int(elem) for elem in s]

    left = []
    total = sum(A)
    for elem in A:
        left.append(total - elem)
        total -= elem

    active = 1
    route = [min(active-A[0], left[0])]
    if route[0] <= 0: 
        if 0 == N and route[0] == 0:
            pass
        else:
            print(-1)
            exit()

    for i in range(1,N+1):
        active = active*2-A[i]
        route.append(min(active, left[i]))
        #print(route[i])
        if route[i] <= 0: 
            if i == N and route[i] == 0:
                break
            else:
                print(-1)
                exit()

    print(sum(route) + sum(A))

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))

if N == 0:
    print(1 if arr[0]==1 else -1)
    exit()
elif arr[0] != 0:
    print(-1)
    exit()

# 末端の葉の数で初期化
sum_arr = [arr[-1]]*N
for i in range(1,N):
	# 深さi+1での頂点数 + 深さiでの葉の数
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
# 本来の順番に反転
sum_arr = sum_arr[::-1]

# 二分木の根から見ていく
ans = [1]*(N+1)
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    ans[i] = tmp

# for i in range(min(25,N+1)):
#     if ans[i] > 2**i:
#         print(-1)
#         exit()
if ans[N] != arr[-1]:
    print(-1)
    exit()

print(sum(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

leaf = sum(A)
ans = 0
node = 1
for i in range(N+1):
    if A[i] > node or leaf == 0:
        ans = -1
        break
    ans += node
    leaf -= A[i]
    node = min(2*(node-A[i]), leaf)
print(ans)

Submission status: Accepted

Solution code:
import sys

N = int(input())
line_data = input()
data = list(map(lambda x: int(x), line_data.split(' ')))

if N == 0:
    if data[0] == 1:
        print(1)
    else:
        print(-1)
    sys.exit(0)

tmp_sum = sum(data)
tmp_data = []
for i in data:
    tmp_sum -= i
    tmp_data.append(tmp_sum)

num = 1
prev_leaf = 1
for i, d in enumerate(data[:-1]):
    tmp = (prev_leaf - d) * 2
    top = tmp_data[i]
    if tmp <= 0:
        num = -1
        break
    if tmp < top:
        prev_leaf = tmp
    else:
        prev_leaf = top
    num += prev_leaf
else:
    if prev_leaf != data[-1]:
        num = -1

print(num)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

b = [0] * (N+1)
b[0] = 1
flag = True

for i in range(N):
    if A[i] > b[i]:
        flag = False

    b[i+1] = (b[i] - A[i]) * 2

if A[N] > b[N]:
    flag = False
ans = 0
l = 0
for i in range(N, -1, -1):
    l += A[i]
    ans += min(l, b[i])

if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
if N == 0:
    print(1 if arr[0]==1 else -1)
    exit()
elif arr[0] != 0:
    print(-1)
    exit()
sum_arr = [arr[-1]]*N
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [1]*(N+1)
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    ans[i] = tmp
for i in range(min(25,N+1)):
    if ans[i] > 2**i:
        print(-1)
        exit()
if ans[N] != arr[-1]:
    print(-1)
    exit()
print(sum(ans))

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
if N == 0:
    if arr[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
else:
    if arr[0] != 0:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    ans[i] = tmp
for i in range(min(25,N+1)):
    if ans[i] > 2**i:
        print(-1)
        exit()
if ans[N] != arr[-1]:
    print(-1)
    exit()
print(sum(ans))

Submission status: Accepted

Solution code:
import math

N = int(input())
# A = list(map(int, input().split()))
A = [int(x) for x in input().split(' ')]


a_max = [0] * (N+1)
a_min = [0] * (N+1)
a = [0] * (N+1)

#１．可・不可の判定
# 最下段からとりうる個数の範囲を考える
#0段目の範囲に１が含まれないならば”不可”(根＝１)

for i in range(N+1):
    if i == 0:
        a_max[N-i] = A[N-i]
        a_min[N-i] = A[N-i]
    else:
        a_max[N-i] = a_max[N-i+1] + A[N-i]
        a_min[N-i] = math.ceil(a_min[N-i+1]/2) + A[N-i]

#check print
# for i in range(N+1):
#     print(str(i) + ':----')
#     print(a_min[i],a_max[i])

#最上段から個数のカウント
for i in range(N+1):
    if i == 0:
        a[i] = 1
    else:
        a[i] = min((a[i-1] - A[i-1])*2 , a_max[i])

#不可は-1を、可は個数の合計を
if a_min[0] > 1:
    print(-1)
else:
    print(sum(a))

Submission status: Accepted

Solution code:
def aaaa():
    n=int(input())
    a=list(map(int, input().split()))
    ans=0
    if a[0]>0:
        if a[0]==1 and n==0:
            return 1
        else:
            return -1
        return -1
    nezen=1
    hazen=0
    line=[]
    liha=[]
    line.append(nezen)
    liha.append(hazen)
    su=0
    su=sum(a[x] for x in range(len(a)))
    for x in range(1,n+1):
        if nezen<=0:
            return -1
        ha=a[x]
        su-=ha
        ne=min(nezen*2-ha,su)
        nezen=ne
        line.append(ne)
        liha.append(ha)
    if line[n]<0:
        return -1
    line[n]=0
    for x in range(len(line)):
        ans+=line[x]+liha[x]
    return ans
print(aaaa())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
k = sum(A)
###syuutenの個数
c = 1  
###考えている列の〇の個数(次の列につながる個数)
aa = 1
ans = 1
if A[0] != 0:
    aa = 2
    if N != 0:
        print(-1)
    else:
        if A[0] == 1:
            print(1)
        else:
            print(-1)
else:
    for i in range(1,N + 1):
        c *= 2
        ##次の列につながる個数の最大値
        if A[i] > c:
            ###A[i]はここが終点になるということ。終点の方が多いことは認められない
            aa = 0
            break
        elif A[i] == c:
            ###終点と同数だとこれより下には繋がらない。もし最下段でなければアウト
            if i != N:
                aa = 0
                break
            else:
                ans += c
        else:
            c -= A[i]
            k -= A[i]
            ans += A[i]
            ###終点の個数を引く。ここで終点の個数だけansを足す
            if c >= k:
                ###次の列につながる個数はこれよりしたにある終点の個数を超えれない
                c = k
            ans += c
            ###この段で下につながる個数を足す

if aa == 0:
    print(-1)
elif aa == 1:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))

SUM = sum(A)

ans = 0
node = 1
for i,leaf in enumerate(A):
    if i == 0:
        non_leaf = 1 - leaf
        ans += 1
        if non_leaf <0:
            print(-1)
            exit()
    else:
        left,right = non_leaf,non_leaf*2
        if SUM < left or non_leaf <= 0:
            print(-1)
            exit()
        node = min(right,SUM)
        ans += node
        non_leaf = node - leaf
        SUM -= leaf
        if non_leaf < 0:
            print(-1)
            exit()

print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    if N == 0:
        if A[0] == 1: return 1
        else: return - 1
    elif A[0] != 0: return - 1
    mx = [0] * (N + 2)
    mx[0] = 1
    mx[N + 1] = 0
    mn = [0] * (N + 2)
    mn[0] = 1
    mn[N + 1] = 0
    n2 = 1
    for i in range(1, N + 1):
        n2 *= 2
        mx[i] = min(n2, (mx[i - 1] - A[i - 1]) * 2)
        mn[i] = mn[i - 1] - A[i - 1]
    for i in range(N, -1, -1):
        tmx = mx[i + 1] + A[i]
        tmn = A[i] + (mn[i + 1] + 1) // 2
        if tmx < 1 or tmx < mn[i]: return -1
        if tmn > mx[i]: return -1
        if tmx < tmn: return -1
        mx[i] = min(mx[i], tmx)
    return sum(mx)

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

if A[0] == 1:
    if len(A) > 1:
        print(-1)
        exit()
    else:
        print(1)
        exit()
elif A[0] > 1:
    print(-1)
    exit()

S = [0] * (N + 2)
for i in range(N, -1, -1):
    S[i] = S[i + 1] + A[i]

sec = [0] * (N + 1)
sec[0] = 1
for i in range(1, N + 1):
    a = A[i]
    v = sec[i - 1] * 2
    if v < a:
        print(-1)
        exit()
    sec[i] = min(v - a, S[i + 1])

print(sum(A) + sum(sec[:-1]))
# print(sec)
# print(A)

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(2*100000) 

def dfs(i,pre,n,a,ans):
    if (pre*2 < a[i]): return -1
    ans[i] += a[i]
    if (i >= n):
        return a[i]

    pre = pre*2 - a[i]
    u = dfs(i+1,pre,n,a,ans);
    if (u<0 or pre*2 < u): return -1;
    ans[i] += min(pre, u)
    return min(pre, u) + a[i]



n = int(input())
a = list(map(int,input().split()))

if (n == 0):
    if (a[0] == 1):
        print(1)
    else:
        print(-1)
    exit()

ans = [1] + [0]*n
u = dfs(1,1,n,a,ans)
if (a[0] != 0): u = -1

if (u >= 0):
    print(sum(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

ans = 0
if N == 0:
    if A[0] >= 2:
        ans = -1
    else:
        ans = 1

if N >= 1 and A[0] >= 1:
    ans = -1

if N >= 1:
    node_num = {N: A[N]}
    max_parent_num = {0: 1}
    for i in range(1, N+1):
        max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]

    for i in range(N, 0, -1):
        if node_num[i] > A[i] + max_parent_num[i]:
            ans = -1
            break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
        if i == 1:
            if node_num[i-1] != 1:
                ans = -1
                break

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)