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

Solution (Python):
n=int(input())
arr=list(map(int,input().split()))
if n==0:
  if arr[0]==1:
    print(1)
  else:
    print(-1)
  exit()
acum=[arr[0]]
for i in range(1,n+1):
  acum.append(acum[-1]+arr[i])
b=[0]*n
b[0]=1-arr[0]
b[0]=min(b[0],acum[n]-acum[0])
for i in range(1,n):
  b[i]=2*b[i-1]-arr[i]
  b[i]=min(b[i],acum[n]-acum[i])
for i in range(n):
  if b[i]<=0:
    print(-1)
    exit()
  if b[i]<=30 and arr[i+1]>2**b[i]:
    print(-1)
    exit()
ans=sum(arr)+sum(b)
print(ans)

Solution (Python):
n=int(input())
arr=list(map(int,input().split()))
ans=sum(arr)
if n==0:
  if arr[0]==1:
    print(1)
  else:
    print(-1)
  exit()
for i in range(n):
  if i<=30 and arr[i]>=2**i:
    print(-1)
    exit()
if n<=30 and arr[n]>2**n:
  print(-1)
  exit()
maxs=[0]*(n+1)
maxs[0]=1
for i in range(1,n):
  maxs[i]=2*maxs[i-1]-arr[i]
tmp=arr[n]
for i in range(n-1,-1,-1):
  maxs[i]=min(maxs[i],tmp)
  tmp+=arr[i]
mins=[0]*(n+1)
for i in range(n-1,-1,-1):
  mins[i]=(mins[i+1]+arr[i+1]+1)//2
for i in range(n):
  if maxs[i]<mins[i]:
    print(-1)
    exit()
ans+=sum(maxs)
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
if N==0:
  if A[0]==1:
    print(1)
  else:
    print(-1)
  exit()
if A[0]:
  print(-1)
  exit()
C=[A[N]]
for i in range(N):
  C.append(C[i]+A[-i-2])
C=C[::-1]
B=[1]
P=1
for i in range(N):
  if (B[i]<<1)<A[i+1]:
    print(-1)
    exit()
  P+=min((B[i]<<1),C[i+1])
  B.append(min((B[i]<<1),C[i+1])-A[i+1])
  if B[-1]<0:
    print(-1)
    exit()
print(P)

Solution (Python):
print(max(-(b:=(c:=sum(a:=[*map(int,[*open(0)][1].split())]))>0),sum((b:=min(c:=c-a,b-a<<1))for a in a)+1))

Solution (Python):
c=sum(a:=[*map(int,[*open(0)][1].split())])
b=1
print(max(-1,sum((b:=min(c:=c-a,b-a<<1))for a in a)+1))

Solution (Python):
*a,=map(int,[*open(0)][1].split())
c=sum(a)
s=b=1
for a in a:c-=a;b=min(c,b-a<<1);s+=b
print(max(-1,s))

Solution (Python):
c=sum(a:=[*map(int,[*open(0)][1].split())])
s=b=1
for a in a:b=min(c:=c-a,b-a<<1);s+=b
print(max(-1,s))

Solution (Python):
*a,=map(int,[*open(0)][1].split())
c=sum(a)
s=b=1
for a in a:c-=a;b=min(c,(b-a)*2);s+=b
print(max(-1,s))

Solution (Python):
c=sum(a:=[*map(int,[*open(0)][1].split())])
s=b=1
for a in a:b=min(c:=c-a,(b-a)*2);s+=b
print(max(-1,s))

Solution (Python):
c=sum(a:=[*map(int,[*open(0)][1].split())])
s=b=1
for a in a:b=min(c:=c-a,2*(b-a));s+=b
print(-(s<0)or s)

Solution (Python):
c=sum(a:=[*map(int,[*open(s:=0)][1].split())])
b=1
for a in a:s=-(b<a)or s+b;b=min(c:=c-a,(b-a)*2)
print(s)

Solution (Python):
*a,=map(int,[*open(s:=0)][1].split())
c=sum(a)
b=1
for a in a:
  if b<a:
    s=-1
    break
  s+=b
  c-=a
  b=min(c,(b-a)*2)
print(s)

Solution (Python):
*a,=map(int,[*open(0)][1].split())
c=[s:=0]
for i in a[:0:-1]:c+=c[-1]+i,
b=1
for a in a:
  if b<a:
    s=-1
    break
  s+=b
  b=min(c.pop(),(b-a)*2)
print(s)

Solution (Python):
import math








import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    l = [0]*(n+1)
    l[n] = (A[n], A[n])
    for i in reversed(range(1, n+1)):
        l[i-1] = (max(math.ceil(l[i][0]/2)+A[i-1], 1), l[i][1]+A[i-1])

    if 1 not in range(l[0][0], l[0][1]+1):
        print(-1)
    else:
        ans = [0]*(n+1)
        ans[0] = 1
        cnt = 1
        for i in range(n):
            ans[i+1] = min((ans[i]-A[i])*2, l[i+1][1])
        print(sum(ans))


resolve()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if n==0:
  if a[0]==1:
    print(1)
    exit()
  else:
    print(-1)
    exit()
if a[0]>0:
  print(-1)
  exit()

ans=1
pre_no_ha=1
all_ha=sum(a)

for ai in a[1:]:
  if pre_no_ha<=0:
    print(-1)
    exit()
  if ai>pre_no_ha*2:
    print(-1)
    exit()
  
  pre_no_ha*=2
  pre_no_ha-=ai
  all_ha-=ai
  pre_no_ha=min(pre_no_ha,all_ha)
  ans+=pre_no_ha+ai

print(ans)

Solution (Python):
import sys
import numpy as np
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
b = [0]*(n+1)
bm = [0]*(n+1)
b[0] = 1
if a[0] > 1:
  print(-1)
  exit(0)
bm[-1] = a[-1]
for i in range(1,n+1):
  bm[-1-i] = bm[-i]+a[-i-1]
  b[i] = (b[i-1]-a[i-1])*2
b = np.array(b)
bm = np.array(bm)
b = np.amin([[b],[bm]], axis=0)
if a[-1] != b[-1,-1]:
  print(-1)
  exit(0)
if np.any(b <= 0):
  print(-1)
  exit(0)
print(np.sum(b))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
import sys

lim = [0]*(n+1)
aa = 0
for i in range(n+1):
    aa += a[n-i]
    lim[n-i] = aa
    
if n == 0:
    if a[0] != 1:
        print(-1)
        sys.exit()
    else:
        print(1)
        sys.exit()
        
if a[0] != 0:
    print(-1)
    sys.exit()
    
ha = [[0]*(n+1) for i in range(2)]
ha[0][0] = 1
ha[1][0] = 1
for i in range(n):
    ha[1][i+1] = min(ha[0][i]*2 , lim[i+1])
    ha[0][i+1] = ha[1][i+1] - a[i+1]
    if ha[0][i+1] <= 0 and i != n-1:
        print(-1)
        sys.exit()
    if ha[0][i+1] < 0 and i == n-1:
        print(-1)
        sys.exit()
        
print(sum(ha[1]))

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    x = 1
    mx = [0] * (N+1)
    for i, a in enumerate(A):
        if i != N and x <= a:
            print(-1)
            return
        if i == N and x < a:
            print(-1)
            return
        x -= a
        mx[i] = x
        x *= 2
    ans = 0
    edge = 0
    for i in range(N+1)[::-1]:
        a = A[i]
        edge = min(edge, mx[i])
        ans += edge + a
        edge += a
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def error():
    print(-1)
    quit()

n = inp()
a = inpl()
if n == 0 and sum(a) == 1:
    print(1)
    quit()
can = [0] * (n+1); can[0] = 1
b = [0] * (n+1)
res = [0] * (n+1)

if a[0] != 0:
    error()

for i in range(n):
    can[i+1] = can[i]*2 - a[i+1]
    if can[i+1] < 0:
        error()
can[-1] = 0
b[-1] = 0
res[-1] = a[-1]
for i in range(n)[::-1]:
    b[i] = min(res[i+1], can[i])
    res[i] = a[i] + b[i]
print(sum(res))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
leaf = sum(a)

if n == 0 and a[0] != 1:
    print(-1)
    exit()
b[0] = 1 - a[0]
leaf -= a[0]
ans = 1
for i in range(1,n+1):
    kosu = min(b[i-1] * 2,leaf)
    ans += kosu
    b[i] = kosu - a[i]
    if b[i] < 0:
        print(-1)
        exit()
    leaf -= a[i]
print(ans)

Solution (Python):
n = int(input())
nums = list(map(int, input().split()))
if n == 0:
  if nums[0] == 1:
    print(1)
  else:
    print(-1)
  exit()
if n > 0 and nums[0] != 0:
  print(-1)
  exit()
n_nods = 1
ans = 1
ret = sum(nums)
for i in range(1,n+1):
  n_nods = min(n_nods*2,ret)
  ans += n_nods
  ret -= nums[i]
  n_nods -= nums[i]
  if n_nods < 0:
    print(-1)
    exit()
  if n_nods == 0 and i < n:
    print(-1)
    exit()
print(ans)

Solution (Python):
import math

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



seq = [[folia[-1], folia[-1]]]
for i in range(n): 
    tmp = folia[-(i+2)]
    sml = math.ceil(seq[i][0] / 2) + tmp 
    big = seq[i][1] + tmp
    seq += [[sml, big]]



if not (seq[-1][0] <= 1 <= seq[-1][1]):
    print(-1)
    exit()


ans =[1]
for j in range(n): 
    tmp = min((ans[j] - folia[j]) * 2, seq[-(j+2)][1])
    ans.append(tmp)
print(sum(ans))

Solution (Python):
import math

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


seq = [[folia[-1], folia[-1]]]

for i in range(n): 
    tmp = folia[-(i+2)]
    sml = math.ceil(seq[i][0] / 2) + tmp 
    big = seq[i][1] + tmp
    seq += [[sml, big]]


if not (seq[-1][0] <= 1 <= seq[-1][1]):
    print(-1)
    exit()

ans =[1]
for j in range(n): 
    tmp = min((ans[j] - folia[j]) * 2, seq[-(j+2)][1])
    ans.append(tmp)
print(sum(ans))

Solution (Python):

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import math

n = readint()
a = readints()

flag = 0

node = [1]
for i in range(n):
    if a[i]>node[-1]:
        flag = 1
        break
    else:
        node.append((node[-1]-a[i])*2)

if a[-1]>node[-1]:
    flag = 1

if flag:
    print(-1)
    exit()

node[n] = a[n]

for i in range(n-1,-1,-1):
    if node[i]>a[i]+node[i+1]:
        node[i] = a[i] + node[i+1]
    else:
        break
print(sum(node))

Solution (Python):
N=int(input())

L=list(map(int,input().split()))

M=[0 for i in range(N+1)]
M[0]=1
if N==0:
    if L[0]==1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if L[0]==1:
    print(-1)
    exit()

for i in range(1,N+1):
    M[i]=M[i-1]*2-L[i]
    if M[i]<0:
        print(-1)
        exit()



M[-1]=0
for i in range(1,N+1):
    if M[-1-i]<(M[-i]+L[-i]+1)//2:
        print(-1)
        exit()
    elif (M[-i]+L[-i])>=M[-1-i] and M[-1-i]>=(M[-i]+L[-i]+1)//2:
        continue
    else:
        M[-1-i]=(M[-i]+L[-i])


print(sum(L)+sum(M))

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

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

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

node = [1]
komoti = [1]
for i in range(1, n+1):
    ai = a[i]
    if komoti[-1]*2 >= ai:
        node.append(min(ruiseki[i], komoti[-1]*2))
        komoti.append(node[-1]-ai)
    else:
        print(-1)
        exit()

print(sum(node))

Solution (Python):

N = int(input())

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


limit = [1]  
for d in range(1, N+1):
    if d == N:  
        limit.append(A[d])
    else:
        limit.append((limit[-1]-A[d-1])*2)
        
        if limit[-1] < 0:
            print(-1)
            exit()


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


ans = [limit[-1]]

now_node = limit[-1]
for d in range(N-1, -1, -1):
    
    ans.append(min(now_node+A[d], limit[d]))  
    now_node = ans[-1]  


ans.reverse()
for d in range(N):
    if (ans[d]-A[d])*2 < A[d+1]:  
        print(-1)
        exit()
print(sum(ans))

Solution (Python):

N = int(input())

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


limit = [1]  
for d in range(1, N+1):
    if d == N:  
        limit.append(A[d])
    else:
        limit.append((limit[-1]-A[d-1])*2)
        
        if limit[-1] < 0:
            print(-1)
            exit()


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


ans = [limit[-1]]

now_node = limit[-1]
for d in range(N-1, -1, -1):
    ans.append(min(now_node+A[d], limit[d]))
    now_node = ans[-1]  


ans.reverse()
for d in range(N):
    if (ans[d]-A[d])*2 < A[d+1]:
        print(-1)
        exit()
print(sum(ans))

Solution (Python):

N = int(input())

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


limit = [1]  
for d in range(1, N+1):
    if d == N:  
        limit.append(A[d])
    else:
        limit.append((limit[-1]-A[d-1])*2)
        if limit[-1] < 0:
            print(-1)
            exit()


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


ans = [limit[-1]]

now_node = limit[-1]
for d in range(N-1, -1, -1):
    ans.append(min(now_node+A[d], limit[d]))
    now_node = ans[-1]  


ans.reverse()
for d in range(N):
    if (ans[d]-A[d])*2 < A[d+1]:
        print(-1)
        exit()
print(sum(ans))

Solution (Python):

"""NOMURA プログラミングコンテスト 2020: C - Folia
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c
"""


def main():
    N = int(input())
    As = list(map(int, input().split()))

    leaves_count = sum(As)
    node_count = 1
    ans = 0
    for i, a in enumerate(As):
        leaves_count -= a
        next_node_count = min(leaves_count, (node_count - a) * 2)
        if next_node_count < 0:
            ans = -1
            break
        ans += node_count
        node_count = next_node_count

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

"""NOMURA プログラミングコンテスト 2020: C - Folia
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c
"""


def main():
    N = int(input())
    As = list(map(int, input().split()))

    leaves_count = sum(As)
    node_count = 1
    ans = 0
    for i, a in enumerate(As):
        leaves_count -= a
        next_node_count = min(leaves_count, (node_count - a) * 2)
        if next_node_count < 0:
            print(-1)
            break
        ans += node_count
        node_count = next_node_count
    else:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.sum(A)-np.cumsum(np.append(0, A[:len(A)-1]))
v=0
k=0
for i in range(N+1):
  if i==0:
    if N==0 and A[0]==1:
      k=1
    elif A[0]==0:
      k=1
    else:
      print(-1)
      break
  elif i==N:
    if B[i]<=2*(k-A[i-1]):
      k=B[i]
    else:
      k=0
      print(-1)
      break
  else:
    k=min(2*(k-A[i-1]),B[i])
    if k<=0:
      print(-1)
      break
  v+=k
if k>0:
  print(v)

Solution (Python):







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


if n == 0:
    if nums[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
if n > 0 and nums[0] >= 1:
    print(-1)
    exit()



rest = sum(nums)

n_node = 1
ans = 1
for i in range(1, n+1):
    
    
    n_node = min(n_node * 2, rest)
    ans += n_node

    
    n_node -= nums[i]
    rest -= nums[i]

    
    if n_node < 0:
        print(-1)
        exit()
    
    if n_node == 0 and i < n:
        print(-1)
        exit()

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
N = sum(a)

s = 1
S = 1
if a[0] > 1 or (a[0] >= 1 and len(a) > 1):
    S = -1
else:
    for i in range(1,n+1):
        if a[i] > 2*s:
            S = -1
            break
        if s*2 <= N:
            S += s*2
            s += s - a[i]
        else:
            S += N
            s += N - s - a[i]
        N -= a[i]
print(S)

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq

from fractions import gcd

MOD = 10 ** 9 + 7




n = int(input())
A = list(map(int, input().split()))
sA = list(itertools.accumulate(A[::-1]))[::-1]


num = 0
par = 1
for i in range(n+1):
    tmp_num = min(par, sA[i])
    if tmp_num <= 0:
        print(-1)
        exit()
    
    num += tmp_num
    par = 2*(tmp_num-A[i])
    

print(-1 if par < 0 else num)

Solution (Python):
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 1:
            print(1)
            exit()
        else:
            end()
    elif a[0]!=0:
        end()

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

    for i in range(n+1):
        if i!=0:
            b[i] = min(2*(b[i-1]-a[i-1]),b[i])
        if b[i]<a[i]:
            end()
    print(sum(b))
    return
 
if __name__=='__main__':
    main()

Solution (Python):
n,*a=map(int,open(0).read().split())
dp=[0]*(n+1)
dp[0]=1
for i,x in enumerate(a):
	if dp[i]<x:
		print(-1)
		exit()
	if i<n:
		dp[i+1]=(dp[i]-x)*2
dp[-1]=a[-1]
for i in range(n,0,-1):
	if dp[i-1]>a[i-1]+dp[i]:
		dp[i-1]=a[i-1]+dp[i]
print(sum(dp))

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

if N == 0 and A[0] != 1:
  print(-1)
elif N != 0 and A[0] != 0:
  print(-1)
else:
  ans = 1
  nodes = 1
  preF = 0
  sucF = sum(A)
  
  for d in range(1, N+1):
    fol = A[d]
    nodes = min((nodes-preF)*2, sucF)
    
    if nodes < fol:
      print(-1)
      exit()
    
    ans += nodes
    preF = fol
    sucF -= fol
  print(ans)

Solution (Python):
import math

ceil = math.ceil

def main(N, A):
    A.reverse()
    pos = [(A[0], A[0])]
    for i in range(len(A)-1):
        tmpmin = ceil(pos[-1][0]/2) + A[i+1]
        tmpmax = pos[-1][1] + A[i+1]
        pos.append((tmpmin, tmpmax))

    l,r = pos.pop()
    if l > 1:
        return -1
    
    ki = [1]
    A.reverse()
    for j in range(N):
        m = (ki[j]-A[j])*2
        l, r = pos.pop()
        if m < l:
            return -1
        ki.append(min(r, m))
    
    return sum(ki)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = main(N, A)
    print(ans)

Solution (Python):
n = int(input())
al = list(map(int, input().split()))
bl = [0]*(n+1)
acc = [0]*(n+2)
for i in range(n+1):
    acc[i+1] = al[i]+acc[i]

res = 0
for d in range(n+1):
    if d==0:
        res += 1
        bl[0] = 1 - al[0]
    else:
        r1 = 2*bl[d-1] - al[d]
        r2 = acc[-1] - acc[d+1]
        bl[d] = min(r1,r2)
        res += al[d]+bl[d]
    if bl[d]<0:
        print(-1)
        exit()

print(res)

Solution (Python):
def solve():
    N = int(input())
    lfs = list(map(int, input().strip().split()))
    ans = 0
    L = 1 << N
    lo = lfs[-1]
    hi = lfs[-1]
    memo = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        if lo > L:
            return -1
        memo[i + 1] = hi
        lo = (lo + 1) // 2 + lfs[i]
        hi = hi + lfs[i]
        L = L >> 1

    if lo > L:
        return -1
    memo[0] = hi
    
    curr = 1
    for i in range(N + 1):
        ans += min(memo[i], curr)
        curr = (curr - lfs[i]) << 1
    return ans

print(solve())

Solution (Python):
from math import ceil

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

bottom_n_list = [(0, 0) for _ in range(n + 1)]
bottom_n_list[n] = (a[n], a[n])
for i in range(n-1, -1, -1):
    leaf_num = a[i]
    min_a_node_num = ceil(bottom_n_list[i + 1][0] / 2)
    max_a_node_num = min(bottom_n_list[i + 1][1], 2 ** i - leaf_num)
    if max_a_node_num < min_a_node_num:
        print(-1)
        exit()
    bottom_n_list[i] = (min_a_node_num + leaf_num, max_a_node_num + leaf_num)

top_n_list = [0]*(n+1)
if 1 < bottom_n_list[0][0] or bottom_n_list[0][1] < 1:
    print(-1)
    exit()
top_n_list[0] = 1
ans = 1
for i in range(1, n+1):
    top_n_list[i] = min(bottom_n_list[i][1], (top_n_list[i-1]-a[i-1])*2)
    ans += top_n_list[i]

print(ans)

Solution (Python):
N = int(input())

A = list(map(int,input().split()))
s = sum(A[1:])
B = [0] * (N+1)
B[0] = 1 - A[0]
for i in range(0,N):
    s -= A[i+1]
    if 2*B[i] < A[i+1]:
        print("-1")
        exit()
    B[i+1] = min(2*B[i]-A[i+1],s)
if B[-1] != 0:
    print("-1")
else:
    print(sum(A)+sum(B))

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

node = 1

leaf = sum(A)
max_node = 1
judge = True
ans = 0
for i, a in enumerate(A):
    ans += node
    leaf -= a
    if node < a+1 and leaf > 0:
        judge = False
        break
    
    max_node = (node - a) * 2
    node = min(leaf, max_node)
    

if judge and max_node == 0:
    print(ans)
else:
    print(-1)

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

s=sum(A)

ans=1
eda=1

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

if A[0]!=0:
  print(-1)
  exit()
  
for i in range(1,N+1):
  if eda*2<=s:
    eda*=2
  else:
    eda=s
  ans+=eda
  eda-=A[i]
  s-=A[i]
  if eda<=0 and i != N:
    print(-1)
    exit()
if eda!=0:
  print(-1)
  exit()
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

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


minV = [0 for i in range(N + 1)]
maxV = [0 for i in range(N + 1)]

minV[-1] = A[-1]
maxV[-1] = A[-1]
for i in range(len(A) - 2, -1, -1):
  leaf = A[i] 
  minV[i] = (minV[i + 1] + 1) // 2 + leaf
  maxV[i] = maxV[i + 1] + leaf

if 1 < minV[0] or maxV[0] < 1:
  print(-1)
  exit(0)


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

print(sum(V))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] != 1:
    print(-1)
    exit(0)
b = [0] * (n + 2)
for i in range(n, 0, -1):
    b[i - 1] = b[i] + a[i]
t = 1 - a[0]
ans = 1
for i in range(n):
    m = min(t * 2, b[i])
    if m < a[i + 1]:
        print(-1)
        exit(0)
    ans += m
    t = m - a[i + 1]
print(ans)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
 
    section_needed = sum(a)
    ans = 0
    section_count = 1
    total_section = 1
    for i in range(n+1):
        ans += section_count
        section_count -= a[i]
        if section_count <= 0 and i != n:
            print(-1)
            return
        if i == n and total_section != section_needed:
            print(-1)
            return
        next_branch = min(max(0, section_needed - total_section), section_count)
        total_section += next_branch
        section_count += next_branch
 
    print(ans)
 
main()

Solution (Python):
from math import ceil
n = int(input())
A = list(map(int,input().split()))[::-1]
mn,mx = A[0], A[0]
step = [[mn,mx]]
for i in range(1, n+1):
    mn = ceil(mn/2) + A[i]
    mx = mx + A[i]
    step.append([mn,mx])
if not mn<=1 and 1<=mx:
    print(-1)
else:
    step = step[::-1]
    A = A[::-1]
    now = 1
    ans = 1
    for i in range(1, n+1):
        now = min(step[i][1],
                  (now-A[i-1])*2)
        ans += now
    print(ans)

Solution (Python):
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

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


pref = [0]*(n+1)
totsum = sum(nmleaves)
pref[0] = totsum
t = 0
for i in range(1, n+1):
    t += nmleaves[i-1]
    pref[i]  = totsum - t

prev_nl = 1
ans = 1
for lev in range(1, n+1):
    nodes = min(prev_nl*2, pref[lev])
    ans += nodes
    prev_nl = nodes - nmleaves[lev]
    if prev_nl < 0:
        print(-1)
        exit()
    elif prev_nl == 0 and lev+1<n+1 and pref[lev + 1]>0:
        print(-1)
        exit()
print(ans)

Solution (Python):
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    n += 1
    a = list(map(int, input().split()))
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i] + a[i]
    ans = [0] * n
    for i in range(n):
        ans[i] = c[n] - c[i]
    if n == 1 and a[0] == 0:
        print(-1)
        return
    if n > 1 and a[0] > 0:
        print(-1)
        return
    ans[0] = min(1, ans[0])
    if ans[0] < a[0]:
        print(-1)
        return
    for i in range(1, n):
        ans[i] = min(ans[i], (ans[i-1]-a[i-1]) * 2)
        if ans[i] < a[i]:
            print(-1)
            return

    print(sum(ans))
main()

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

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

b = [0 for _ in range(n)]
b.append(a[-1])
for i in range(n)[::-1]:
   b[i] = b[i+1] + a[i]

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

print(ans)

Solution (Python):
N = int(input())
nums = list(map(int, input().split()))
nodes = []
currentLeaf = 1
fail = False

for i in range(N + 1):
	nodes.append(currentLeaf)
	currentLeaf = (currentLeaf-nums[i])*2
	if (currentLeaf < 0):
		fail = True
		break 
if (fail):
	print(-1)
else:
  
  currentLeaf = 0
  totalNode = 0
  for i in reversed(range(N+1)):
      currentLeaf += nums[i]
      currentLeaf = min(currentLeaf, nodes[i])
      totalNode += currentLeaf

  if (fail):
      print(-1) 
  else:
      print(totalNode)

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

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

B=[0 for _ in range(N)]

B.append(A[-1])
for i in range(N)[::-1]:
    B[i]=B[i+1]+A[i]

r=1
ans=1
for i in range(1,N+1):
    t=min(r*2,B[i])
    ans+=t
    r=t-A[i]
    if r<0:
        print(-1)
        exit()

print(ans)

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A == [0]:
            print('0')
        elif A == [1]:
            print('1')
        else:
            print('-1')
        return

    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')
        return

    if A[0] != 0:
        print('-1')
        return

    f = [0 for i in range(N)]

    f[0] = 1
    count = sum(A) - 1

    for d in range(1, N):
        f[d] = 2 * min(f[d - 1], count) - A[d] + min(max(f[d - 1] - count, 0), f[d - 1])
        count -= min(f[d - 1], count)
        if f[d] <= 0:
            print('-1')
            return

    if A[-1] > 2 * f[N-1]:
        print('-1')
        return

    print(sum(f) + sum(A))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  
    solve(N, A)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if a[0]:
  if n==0 and a[0]==1:
    print(1)
  else:
    print(-1)
  exit()
b=[0]*n
b.append(a[-1])
for i in range(n)[::-1]:
  b[i]=b[i+1]+a[i]
ro=1
ans=1
for i in range(1,n+1):
  t=min(ro*2,b[i])
  ans+=t
  ro=t-a[i]
  if ro<0:
    print(-1)
    exit()
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
bunretsu = sum(A) - 1
zanretsu = 1
souwa = 0
for i in range(N+1):
    souwa += zanretsu
    if A[i] <= zanretsu:
        zanretsu -= A[i]
    else:
        souwa = -1
        break
    if bunretsu >= 1 and bunretsu <= zanretsu:
        zanretsu += bunretsu
        bunretsu = 0
    elif bunretsu >= 1 and bunretsu > zanretsu:
        bunretsu -= zanretsu
        zanretsu *= 2
print(souwa)

Solution (Python):
import operator
from itertools import accumulate

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A_sum = list(reversed(list(accumulate(reversed(A))))) + [0]
  B = [0] * (N+1)

  B[0] = 1 - A[0]
  d = A_sum[0] + B[0]
  if B[0] < 0:
    return -1
  for i in range(1, N+1):
    B[i] = min(B[i - 1] * 2 - A[i], A_sum[i+1])
    
    if B[i] < 0:
      return -1
    d += B[i]
  return d

print(main())

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul

mod = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

n = I()
A = LI()
max_ret = 0
min_ret = 0
max_arr = [0] * (n + 1)
min_arr = [0] * (n + 1)
for i in range(n, -1, -1):
    max_ret = max_ret + A[i]
    min_ret = (min_ret + 1) // 2 + A[i]
    max_arr[i] = max_ret
    min_arr[i] = min_ret

if max_ret >= 1 >= min_ret:
    ans = 1
    ret = 1
    for j in range(1, n + 1):
        ret = min((ret - A[j-1]) * 2, max_arr[j])
        ans += ret
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul

mod = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

n = I()
A = LI()
max_ret = 0
min_ret = 0
max_arr = [0] * (n + 1)
min_arr = [0] * (n + 1)
for i in range(n, -1, -1):
    max_ret = max_ret + A[i]
    min_ret = (min_ret + 1) // 2 + A[i]
    max_arr[i] = max_ret
    min_arr[i] = min_ret

if max_ret >= 1 >= min_ret:
    ans = 1
    ret = 1 - A[0]
    for j in range(1, n + 1):
        ret = min(ret * 2, max_arr[j])
        ans += ret
        ret -= A[j]
    print(ans)
else:
    print(-1)