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())
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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]

c = [1]*(n+1)
for i in range(n):
  c[i+1] = (c[i]-a[i])*2

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)

Solution (Python):
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()

Solution (Python):
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
        
        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()

Solution (Python):
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)

Solution (Python):
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]))
        
        if route[i] <= 0: 
            if i == N and route[i] == 0:
                break
            else:
                print(-1)
                exit()

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

Solution (Python):
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





if ans[N] != arr[-1]:
    print(-1)
    exit()

print(sum(ans))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
import math

N = int(input())

A = [int(x) for x in input().split(' ')]


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





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]







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])


if a_min[0] > 1:
    print(-1)
else:
    print(sum(a))

Solution (Python):
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())

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

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:
            
            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]
            
            if c >= k:
                
                c = k
            ans += c
            

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

Solution (Python):
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)

Solution (Python):
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())

Solution (Python):
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]))

Solution (Python):
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)

Solution (Python):
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
        
        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)

Solution (Python):







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

ans=0
bef=0

tmp=[]



for i in range(N+1):
    if i==0:
        if A[0]==1:
            bef=0
        elif A[0]>1:
            print("-1")
            exit()
        elif N==0 and A[0]==0:
            print("-1")
            exit()
        else:
            bef=1
        tmp.append(1)
        continue
    elif (bef*2-A[i])>=0:
        bef=bef*2-A[i]
        tmp.append(bef)
    else:
        print("-1")
        exit()

hoge=[]

for i in range(N+1):
    current=A[-(i+1)]
    if i==0:
        bef=current
        ans+=current
        hoge.append(bef)
        continue
    else:
        tmpp = tmp[-(i+1)]
        if bef > tmpp:
            ans+=tmpp+current
            bef=tmpp+current
        else:
            ans+=current+bef
            bef=current+bef
    hoge.append(bef)

if ans==0:
    ans=-1


print(ans)

Solution (Python):
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)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

import math


limits = [(A[-1], A[-1])]

for i in reversed(range(0, N)):
    min_ = math.ceil(limits[-1][0] / 2)
    max_ = limits[-1][1]
    
    limits.append((min_ + A[i], max_ + A[i]))

if limits[-1][0] != 1:
    print(-1)
    quit()


limits.reverse()


tree = [1]
for i in range(1, N+1):
    nodes = min(2 * (tree[-1] - A[i-1]), limits[i][1])
    tree.append(nodes)



ans = sum(tree)
print(ans)

Solution (Python):
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

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


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


maxNonLeafs[N] = 0
for i in range(N - 1, -1, -1):
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])


count = 0
for i in range(N + 1):
    count += maxNonLeafs[i] + numLeafs[i]
print(count)

Solution (Python):

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = [0] * len(A)
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(range(len(A)-1)):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    if num_of_node < min_maxs[index][0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()

Solution (Python):

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = [0] * len(A)
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(range(len(A)-1)):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    if num_of_node < min_maxs[index][0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()

Solution (Python):
def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = [0] * len(A)
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(range(len(A)-1)):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    if num_of_node < min_maxs[index][0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()

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

n = int(input())
a = [int(x) for x in input().split()]

max_a = [0]*(n + 1)
"""
if n == 0 and a[0] == 0:
    print(-1)
    sys.exit()
"""
for i in range(n + 1):
    if i == 0:
        max_a[i] = 1
    else:
        max_a[i] = (max_a[i - 1] - a[i - 1])*2
        if max_a[i] < 0:
            print(-1)
            sys.exit()

for i in range(n, -1, -1):
    if i == n:
        if max_a[i] < a[i]:
            print(-1)
            sys.exit()
        max_a[i] = a[i]
    else:
        min_p = max_a[i + 1] // 2 + int(max_a[i + 1] % 2 == 1)
        max_p = max_a[i + 1]
        if max_a[i] < min_p:
            print(-1)
            sys.exit()
        max_a[i] = min(max_p + a[i], max_a[i])
print(sum(max_a))

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

n = int(input())
a = [int(x) for x in input().split()]

max_a = [0]*(n + 1)

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

for i in range(n + 1):
    if i == 0:
        max_a[i] = 1
    else:
        max_a[i] = (max_a[i - 1] - a[i - 1])*2
        if max_a[i] < 0:
            print(-1)
            sys.exit()

for i in range(n, -1, -1):
    if i == n:
        if max_a[i] < a[i]:
            print(-1)
            sys.exit()
        max_a[i] = a[i]
    else:
        min_p = max_a[i + 1] // 2 + int(max_a[i + 1] % 2 == 1)
        max_p = max_a[i + 1]
        if max_a[i] < min_p:
            print(-1)
            sys.exit()
        max_a[i] = min(max_p + a[i], max_a[i])
print(sum(max_a))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
V = [0]*(N+1)
flug = 0
Lsum= sum(A)
 
V[0] = 1
for i in range(N):
    V[i+1] = (V[i]*2 - A[i+1])
    if V[i+1] < 0 :
        flug = 1
    Lsum = Lsum - A[i+1]
    if V[i+1] > Lsum :
        V[i+1] = Lsum
 
ans = sum(V)+sum(A)
if A[0] != 0 or A[N] == 0:
    ans = -1
if flug == 1:
   ans = -1
if N == 0 and A[0] != 1:
    ans = -1
elif N == 0 and A[0] == 1:
    ans = 1
 
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate

    n = int(input())
    a = list(map(int, readline().split()))
    a_cum = [0] * (n + 1)
    a_cum[n] = a[n]

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

    b = [0] * (n + 1)
    b[0] = 1

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

    ans = 0
    for i in range(n + 1):
        if b[i] < a[i]:
            print(-1)
            sys.exit()
        ans += b[i]

    print(ans)


if __name__ == '__main__':
    main()

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

MAX = [1] * (N+1)
ans = [0] * (N+1)
INF = 10**15

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

for i in range(1, N+1):
    MAX[i] = min((MAX[i-1] - A[i-1]) * 2, INF)
    if MAX[i] < A[i]:
        print(-1)
        exit()

ans[N] = A[N]

for i in reversed(range(N)):
    ans[i] = min(ans[i+1]+A[i], MAX[i])

print(sum(ans))

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
g=[1]
for i in range(n):
  
  
  g+=[(g[-1]-l[i])*2]
a=0
t=0

for i in range(n,-1,-1):
  
  if l[i]>g[i]:
    print(-1)
    break
  
  
  t=min(l[i]+t,g[i])
  
  a+=t
else:
  print(a)

Solution (Python):
N = int(input())
a_list = [int(a) for a in input().split()]

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

ans = 1
temp1 = [""]*(N+1)
temp1[-1] = a_list[-1]
for n in range(N-1, 0, -1):
    temp1[n] = temp1[n+1]+a_list[n]
    
temp2 = 1
for n in range(1, N+1):
    temp2 = (temp2-a_list[n-1])*2

    ans_temp = min(temp2, temp1[n])
    temp2 = min(temp2, temp1[n])
    
    if ans_temp < a_list[n]:
        print(-1)
        exit()
    
    ans += ans_temp
    
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
l = [1]
for i in range(n + 1):
    s -= a[i]
    m = min(s, (l[i] - a[i]) * 2)
    if m < 0:
        print(-1)
        exit()
    l.append(m)
print(sum(l))

Solution (Python):

 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()
L = [1]
if a[-1] > 2**n:
    print(-1)
    quit()
if n == 0:
    if a[0] == 0:
        print(-1)
        quit()
L2 = [a[-1]]
for i in range(n)[::-1]:
    L2.append(min(L2[-1] + a[i], 2**i))
L2 = L2[::-1]
ans = 0
for i in range(n+1):
    if i == 0:
        tmp = 1
    else:
        tmp = (L[-1] - a[i-1]) * 2
    if tmp <= 0:
        print(-1)
        quit()
    ans += min(tmp, L2[i])
    L.append(tmp)
if L[-1] - a[-1] < 0:
    print(-1)
    quit()
print(ans)

Solution (Python):
def main():
    n = int(input())
    A = list(map(int, input().split()))

    if n  == 0:
        if A[0] == 1:
            return 1
        else:
            return -1
    elif A[0] != 0:
        return -1
    
    bound = [0]*(n+1)
    bound[n] = A[n]
    for i in range(n-1, -1, -1):
        bound[i] = bound[i+1] + A[i]

    B = [0] * (n+1)
    for i in range(n+1):
        if i == 0:
            B[i] = 1
        else:
            above = (B[i-1] - A[i-1]) * 2
            if  (i < n and above <= 0) or above < 0:
                return -1
            B[i] = min(above, bound[i])
    if B[n] < A[n]:
        return -1
    
    return sum(B)

print(main())

Solution (Python):
from sys import exit
from collections import deque
N = int(input())
D = deque(map(int, input().split()))
if N == 0:
  d = D.pop()
  if d == 1:
    print(1)
  else:
    print(-1)
  exit()
R = [[] for i in range(N + 1)]
leaf = D.pop()
R[-1].append(leaf)
R[-1].append(leaf)
for i in range(N - 1, -1, -1):
  leaf = D.pop()
  R[i].append(R[i + 1][0]//2 + R[i + 1][0] % 2 + leaf)
  R[i].append(R[i + 1][1] + leaf)
  R[i].append(leaf)
if not(R[0][0] <= 1 <= R[0][1]):
  print(-1)
  exit()
node = 1
ans = 1
for i in range(1, N + 1):
  node = min(R[i][1], 2 * (node - R[i-1][2]))
  ans += node
print(ans)

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

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

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

lst = [1]
for i in range(1, n+1):
    lst.append(min((lst[i-1]-a[i-1])*2, sita_maxi[i]))
    if lst[-1] < a[i]:
        print(-1)
        exit()

print(sum(lst))

Solution (Python):
import sys
N=int(input())
alist=list(map(int,input().split()))

if N==0 and alist[0]!=1:
  print(-1)
  sys.exit(0)
elif N>0 and alist[0]>0:
  print(-1)
  sys.exit(0)


blist=[0]*(N+1)
for d in reversed(range(1,N+1)):
  if d>50:
    blist[d-1]=alist[d]+blist[d]
  else:
    blist[d-1]=min(alist[d]+blist[d],(1<<(d-1))-alist[d-1])
  if blist[d-1]<0:
    print(-1)
    sys.exit(0)
  
  

cmax_bu=[0]*(N+1)
for d in range(N+1):
  cmax_bu[d]=alist[d]+blist[d]


pow2d=1
blist=[0]*(N+1)
if alist[0]==0:
  blist[0]=1
for d in range(1,N+1):
  if pow2d<10**10:
    pow2d<<=1
    c=min(2*blist[d-1],pow2d,cmax_bu[d])
  else:
    c=min(2*blist[d-1],cmax_bu[d])
  blist[d]=c-alist[d]
  if blist[d]<0:
    print(-1)
    sys.exit(0)


answer=0
for i in range(N+1):
  answer+=alist[i]+blist[i]
  
print(answer)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * (N + 1)
    if A[0] >= 2:
        print(-1)
        exit()
    if A[0] == 1:
        if len(A) == 1:
            print(1)
            exit()



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

        B[i] = tmp
    ans += A[N]
    C = [0] * (N+1)

    C[N] += A[N]
    for i in range(N-1,0,-1):
        
        if C[i+1] + A[i] <= B[i]:
            ans += A[i] + C[i+1]
            C[i] = A[i] + C[i+1]
        else:
            ans += B[i]
            C[i] = B[i]
            
    print(ans)
        







if __name__ == "__main__":
    main()

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

rng = [[A[N], A[N]]]

for i in range(N - 1, -1, -1):
    merged = (rng[-1][0] + 1) // 2 + A[i]
    nonmerged = rng[-1][1] + A[i]
    rng.append([merged, nonmerged])
if rng[-1][0] > 1:
    print(-1)
    exit()
rng.reverse()
prev_non_leaf = 1
ans = 1
for i in range(1, N + 1):
    _, u = rng[i]
    ans += min(prev_non_leaf * 2, u)
    prev_non_leaf = prev_non_leaf * 2 - A[i]
print(ans)

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

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

ans = 0
v = 0
for i in range(N, -1, -1):
    if Pmax[i]*2 < v:
        ans = -1
        break
    v = min(v, Pmax[i])+A[i]
    ans += v

print(ans)

Solution (Python):
from itertools import accumulate
n = int(input())
As = list(map(int, input().split()))

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


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

b = 1
ans = 1
acc = list(accumulate(As))
s = acc[-1]
for ac,a in zip(acc[1:], As[1:]):
    
    b = min(2*b-a, s-ac)
    if b < 0:
        print(-1)
        exit()
    ans += b+a
print(ans)

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

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

ans = 0
li = [0]*(n+1)

for i,a in enumerate(a_li):
  ans += (i+1)*a

for i,a in enumerate(a_li[::-1]):
  if i >= 1:
    li[i] = li[i-1]+a
  else:
    li[i] = a

li = li[::-1]

flag = True
ne = 0.5
for i in range(n+1):
  if li[i]  > 2*ne:
    ans -= li[i] -int(2*ne)

  
  ne = min(li[i] - a_li[i],int(2*ne)-a_li[i])

  if (i == n and ne != 0) or (i != n and ne <= 0):
    flag = False

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

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






p = As[-1]
q = As[-1]
Asr = As[::-1]
qs = [q]

for j,a in enumerate(Asr[1:]):
    i = n - (j + 1) 
    p = (p+1)//2 + a 
    q = min(q + a, 2**i)

    
    if p > 2**i:
        print(-1)
        exit()
    
    
    qs.append(q)    
    
if p != 1:
    print(-1)
    exit()
qs.reverse()

qs[0] = 1
ans = 1
for i in range(1,n+1):
    if qs[i] > 2**i:
        qs[i] = 2 ** i
    if qs[i] > 2*(qs[i-1]-As[i-1]):
        qs[i] = 2 * (qs[i-1]-As[i-1])
    ans += qs[i]
print(ans)

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

error = False
capacity = [0]
cap = 1
for i, a in enumerate(A):
    cap = cap - a
    if cap < 0:
        error = True
        break
    capacity.append(cap)
    cap *= 2

if error:
    print(-1)
else:
    total = 0
    carry = 0
    for d in range(N, -1, -1):
        cap = capacity[d]
        a = A[d]
        check = carry + a
        if check <= cap:
            total += check
            carry += a
        else:
            total += check
            carry = cap

    print(total)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import accumulate

n = int(readline())
a = list(map(int, readline().split()))
cumsum = list(accumulate(a[::-1]))
ans = 0
check = 1
for aa, v in zip(a, cumsum[::-1]):
    if aa > check:
        print(-1)
        exit()
    else:
        ans += min(check, v)
        check -= aa
        check *= 2
print(ans)

Solution (Python):

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(int(x) for x in readline().split())



leaf = sum(A) 
tmp = 1 
ans = 0 
for a in A:
    
    if tmp < a:
        ans = -1
        break
    
    ans += min(tmp, leaf) 
    
    leaf -= a 
    tmp -= a 
    
    tmp *= 2

print(ans)

Solution (Python):

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = {}
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(range(len(A)-1)):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]
  
    
  
  

  
  
  
  
  
  
  

  
  

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    
    if num_of_node < min_maxs[index][0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()