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())
data = list(map(int, input().split()))

max_edge = []
for depth, a in enumerate(data):
    if depth == 0:
        edge = 1 - a
    else:
        edge = max_edge[depth-1]*2 - a
    
    if edge < 0:
        print(-1)
        exit()
    max_edge.append(edge)

ans = 0
prev_edges = 0
for idx in range(n, -1, -1):
    a = data[idx]
    cap = max_edge[idx]
    if prev_edges > 2*cap:
        print(-1)
        exit()
    edges = min(prev_edges, cap) + a
    ans += edges
    prev_edges = edges

print(ans)

Solution (Python):
n,*a=map(int,open(0).read().split())
t,v=sum(a),[1]
for q in a:
  v+=[min(2*(v[-1]-q),t:=t-q)]
  if v[-1]<0:print(-1);exit()
print(sum(v))

Solution (Python):
n,*a=map(int,open(0).read().split())
t,v=sum(a),[1]
for q in a:
    v+=[min(2*(v[-1]-q),t:=t-q)]
    if v[-1]<0:print(-1);exit()
print(sum(v))

Solution (Python):
import numpy as np
import math
import collections

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


ans = 0
node_num = 1
pre_node_num = 1
B = [1 - A[0]]
ruisekiA = [0 for i in range(N + 2)]
ruisekiA[N] = A[N]
ruisekiA[N + 1] = 0
for i in range(N - 1, -1, -1):
    ruisekiA[i] = ruisekiA[i + 1] + A[i]


for i in range(1, N + 1):
    tmpB = min(2 * B[i - 1] - A[i], ruisekiA[i + 1])
    
    if (tmpB < 0) or (tmpB < B[i - 1] - A[i]):
        ans = -1
        break
    if i == N:
        tmpB = 0
    B.append(tmpB)

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

if ans != -1:
    ans = sum(A) + sum(B)
print(ans)

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

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

As_r = As[::-1]
p = As_r[0]

a_pre = p
qs = [p]

mn = As_r[0]




for i,a in enumerate(As_r[1:]):
    d = min(n - i - 1, 50)
    p = min(2**d, p + a)
    mn = (mn+1)//2 + a
    a_pre = a
    qs.append(p)

if mn != 1:
    print(-1)
    exit()

qs.reverse()

ans = qs[0]
cnt = qs[0]

for i in range(1,n+1):
    qs[i] = min(qs[i-1]*2, 2*(qs[i-1]-As[i-1]),qs[i])
print(sum(qs))

Solution (Python):
from itertools import accumulate
n=int(input())
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)


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

    if n==0:
        if a[0]!=1:
            print(-1)
        else:
            print(1)
    elif b[n]!=a[n]:
        print(-1)
    else:
        print(sum(b))
        
f()

Solution (Python):
import sys
import itertools

ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())

N = ni()
A = nl()
assert len(A) == (N + 1)


def solve():
    ar = list(itertools.accumulate(A[::-1], initial=0))
    ar.reverse()
    assert len(ar) == (N + 2)
    if N == 0:
        return 1 if A[0] == 1 else -1
    if A[0] != 0:
        return -1
    inn = ans = 1
    for i in range(1, N + 1):
        b = 2 * inn - A[i]
        if b < 0:
            return -1
        inn = min(b, ar[i + 1])
        ans += inn + A[i]
    return ans


print(solve())

Solution (Python):
import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()
dbg = lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)

N = ni()
A = nl()
assert len(A) == (N + 1)


def solve():
    ar = list(itertools.accumulate(A[::-1]))
    ar.reverse()
    ar.append(0)
    assert len(ar) == (N + 2)
    if N == 0:
        return 1 if A[0] == 1 else -1
    if A[0] != 0:
        return -1
    inn = ans = 1
    for i in range(1, N + 1):
        b = 2 * inn - A[i]
        if b < 0:
            return -1
        inn = min(b, ar[i + 1])
        ans += inn + A[i]
    return ans


print(solve())

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

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

    if (mx <= 0 and i != n) or (mx < 0 and i == n):
        print(-1)
        exit()
    mx *= 2

a.reverse()
m.reverse()
m[0] = a[0]
for i in range(1, n+1):
    m[i] = min(m[i], m[i-1]) + a[i]

print(sum(m))

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

acc_r = list(accumulate(As[::-1]))
acc_r = acc_r[::-1]

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

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

Solution (Python):
from math import ceil
def solve():
    N = int(input())
    A = list(map(int,input().split()))

    mx = [0] * (N+1)
    mn = [0] * (N+1)

    mx[-1] = A[-1]
    mn[-1] = A[-1]

    for i in range(N-1,-1,-1):
        mx[i] = mx[i+1] + A[i]      
        mn[i] = ceil(mn[i+1]/2) + A[i]
    
    if not mn[0] <= 1 <= mx[0]:
        print(-1)
        return

    ans = 1
    now = 1
    piyo = [1]
    for i in range(1,N+1):
        nxt = (now-A[i-1]) * 2
        piyo.append(nxt)
        ans += min(mx[i],nxt)
        now = nxt

    print(ans)
    
if __name__ == '__main__':
    solve()

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

Solution (Python):
import math

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

up = [[] for _ in range(N+1)] 
up[N] = [A[N],A[N]]

for i in reversed(range(N)):
    Min, Max = up[i+1]
    
    Min_n = math.ceil(Min/2) + A[i]
    Max_n = Max + A[i]
    
    up[i] = [Min_n, Max_n]


if up[0][0] >= 2:
    print(-1)
else:
    down = 1
    
    ans = 1
    for i in range(1, N+1):
        down *= 2
        down = min(down,up[i][1]) - A[i]
        ans += down + A[i]
    print(ans)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
if n==0:
    print(1 if A[0] == 1 else -1)
    exit()
if A[0]>0:
    print(-1)
    exit()
if A[-1]>2**n:
    print(-1)
    exit()
node1=[0]*(n+1)
node1[0]=1
node2=[0]*(n+1)
node2[-1]=A[-1]
for i in range(n):
    x=(node1[i]-A[i])*2
    if x<1:
        print(-1)
        exit()
    node1[i+1]=x

for i in range(n-1,-1,-1):
    x=(node2[i+1]+A[i])
    node2[i]=x
ans=[]

for i in range(n+1):
    x=min(node1[i],node2[i])
    if x<A[i]:
        print(-1)
        exit()
    ans.append(x)
print(sum(ans))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
ans=0
f=[1]*(N+1)
las=A[N]
g=[las]*(N+1)
flag=1
for i in range(0,N):
    f[i+1]=2*(f[i]-A[i])
for i in range(N,0,-1):
    g[i-1]=g[i]+A[i-1]

for i in range(N+1):
    if min(f[i],g[i])<=0:
        flag=0
        break
    ans=ans+min(f[i],g[i])
if g[N]>f[N]:
    flag=0
if flag==0:
    print(-1)
else:
    print(ans)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
if n==0:
    print(1 if A[0] == 1 else -1)
    exit()
if A[0]!=0:
    print(-1)
    exit()
node1=[0]*(n+1)
node1[0]=1
node2=[0]*(n+1)
node2[0]=1
node2[-1]=A[-1]
for i in range(n):
    x=(node1[i]-A[i])*2
    node1[i+1]=x

for i in range(n,0,-1):
    x=(node2[i]+A[i-1])
    node2[i-1]=x

ans=[]

for i in range(n+1):
    x=min(node1[i],node2[i])
    if x<A[i]:
        print(-1)
        exit()
    ans.append(x)
print(sum(ans))

Solution (Python):
from itertools import accumulate
N = int(input())
a = tuple(map(int,input().split()))
s = list(accumulate(a))
b = [0]*(N+1)
if N == 0 and a[0] > 1:
    print(-1)
    exit()
if a[0] == 0:
    b[0] = 1
ans = 1
flag = 0
for d in range(1,N+1):
    b[d] = b[d-1]-a[d]
    tmp = min(s[-1]-s[d],2*b[d-1]-a[d])
    if b[d] > tmp or tmp < 0:
        flag = 1
        break
    else:
        b[d] = tmp
if flag:
    print(-1)
else:
    print(s[-1]+sum(b))

Solution (Python):
import math
def solve():

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

    if(N == 0 and A[0] == 1):
        print(1)
        return
    
    leaf_list = [0] * (N+1)
    

    for d in range(N, -1 , -1):
        if(d == N):
            leaf_list[d] = (A[d],A[d])
        else:
            Min = math.ceil(leaf_list[d+1][0]/2) + A[d]
            Max = leaf_list[d+1][1] + A[d]
            leaf_list[d] = (Min,Max)
            
    if(not(leaf_list[0][0] <= 1 and leaf_list[0][1] >= 1)):
        print(-1)
        return
            
    node_list = [0] * (N+1)
    node_list[0] = 1
    
    for d in range(1, N+1):
        node_list[d] = min((node_list[d-1] - A[d-1]) * 2, leaf_list[d][1])
        
    print(sum(node_list))
solve()

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

Solution (Python):
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
if a[0]==1 and n==0:
    print(1)
    exit()
if a[0]>0:
    print(-1)
    exit()
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
B = [0]*(N+1)

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

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


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

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

ans = 0

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



node_list_1 = [0] * (n + 1)
node_list_2 = [0] * (n + 1)

node_list_1[n] = a[n]
node_list_2[0] = 1

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

for j in range(1, n+1):
    node_list_2[j] = (node_list_2[j-1] - a[j-1]) * 2
    if node_list_2[j] < a[j]:
        print(-1)
        exit()

for k in range(n+1):
    ans += min(node_list_1[k], node_list_2[k])

print(ans)

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

max_edge_num = pow(2,n)

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

total_lost = 0
remained_alls = [1]

for depth in range(1,n+1):
    total_lost *= 2
    full_nodes = pow(2,depth)
    remained_nodes = full_nodes - total_lost
    remained_alls.append(remained_nodes)
    if a[depth] > remained_nodes:
        print(-1)
        sys.exit()
    else:
        total_lost += a[depth]

max_nodes_all = [a[n]]

for depth in range(n-1,0,-1):
    possible = max_nodes_all[-1]
    now = min(possible+a[depth],remained_alls[depth])
    max_nodes_all.append(now)

max_nodes_all.append(1)

answer = 0
for nodes in max_nodes_all:
    answer+=nodes

print(answer)

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

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

t=len(A)-1
for i in range(t):
    B[i] = b
    if 2*(b - A[i]) < A[i+1]:
        count += 1
        break
    b = 2*(b - A[i])
B[n] = b

if n == 0 and A[0] > 1:
    count += 1

j = 0
while count == 0 and A[t] > B[j]:
    if j == n:
        break
    j += 1

total = 0
for i in range(j):
    total += B[i]

s = A[t]
for i in range(t-1,j-1,-1):
    total += min(B[i],s+A[i])
    s+=A[i]

if count==0:
    print(total+A[t])
else:
    print('-1')

Solution (Python):



def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    rem = sum(A)
    cur = 1
    ret = 0
    for a in A:
        cur = min(rem, cur)
        rem -= a
        ret += cur
        cur = 2*(cur-a)
        if cur < 0:
            ret = -1
            break

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
import sys
import math

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    mi = [A[-1]]
    ma = [A[-1]]
    for i in reversed(range(n)):
        mi.append(math.ceil(mi[-1] / 2) + A[i])
        ma.append(ma[-1] + A[i])

    mi = mi[::-1]
    ma = ma[::-1]

    res = []
    for i in range(n + 1):
        if i == 0:
            if mi[i] <= 1 <= ma[i]:
                res.append(1)
                continue
            else:
                break

        if mi[i] <= (res[-1] - A[i - 1]) * 2 <= ma[i]:
            res.append((res[-1] - A[i - 1]) * 2)
        else:
            res.append(ma[i])

    print(sum(res) if len(res) != 0 else -1)


if __name__ == '__main__':
    resolve()

Solution (Python):
from sys import stdin

a=int(stdin.readline())
A=stdin.readline().split()
sum=0
for k in range(0,a+1):
    sum+=int(A[k])

sum-=int(A[a])
ver=1
lay=1
K=0
T=0

if a==0:
    if A[0]!='1':
        print(-1)
        K=1
    else:
        print(1)
        K=1

for l in range(0,a):
    if lay-int(A[l])<=0:
        print(-1)
        K=1
        break
    if (lay-int(A[l]))*2<int(A[a]) and l==(a-1):
        print(-1)
        K=1
        break
    if (lay-int(A[l]))*2-sum+int(A[l])<=int(A[a]):
        lay=(lay-int(A[l]))*2
        ver+=lay
        sum-=int(A[l])
        T=l
    else:
        lay-=int(A[l])
        sum-=int(A[l])
        x=lay-sum-int(A[a])
        if x==0:
           ver+=lay
        elif x>0:
            print(-1)
            K=1
        else:
           lay=sum+int(A[a])
           ver+=lay
        T=l
        break

if K==0:
    for u in range(T+1,a):
        lay -= int(A[u])
        sum -= int(A[u])
        ver+=lay

if K==0:
    print(ver)

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

ans = 0
nodes_min = [0] * (n + 1)
nodes_max = [0] * (n + 1)
nodes_min[n] = leaves[n]
nodes_max[n] = leaves[n]

for depth in range(n, 0, -1):
    root_min = nodes_min[depth] // 2 + nodes_min[depth] % 2
    nodes_min[depth - 1] = leaves[depth - 1] + root_min
    root_max = nodes_max[depth]
    nodes_max[depth - 1] = leaves[depth - 1] + root_max
nodes = [0] * (n + 1)
nodes[0] = 1
for depth in range(n):
    roots = nodes[depth]-leaves[depth]
    if nodes[depth] < nodes_min[depth]:
        print(-1)
        break
    nodes[depth + 1] = min(roots * 2, nodes_max[depth + 1])
else:
    if nodes[n] < nodes_min[n]:
        print(-1)
    else:
        print(sum(nodes))

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

ans = 0
nodes_min = [0] * (n + 1)
nodes_max = [0] * (n + 1)
nodes_min[n] = leaves[n]
nodes_max[n] = leaves[n]

for depth in range(n, 0, -1):
    root_min = nodes_min[depth] // 2 + nodes_min[depth] % 2
    nodes_min[depth - 1] = leaves[depth - 1] + root_min
    root_max = nodes_max[depth]
    nodes_max[depth - 1] = leaves[depth - 1] + root_max
nodes = [0] * (n + 1)
nodes[0] = 1
for depth in range(n):
    roots = nodes[depth]-leaves[depth]
    if nodes[depth] < nodes_min[depth]:
        print(-1)
        break
    nodes[depth + 1] = min(roots * 2, nodes_max[depth + 1])
else:
    if nodes[n] < nodes_min[n]:
        print(-1)
    else:
        print(sum(nodes))

Solution (Python):
import sys
import math
n = int(input())
A = list(map(int, input().split()))
NODE_RANGE = [0 for i in range(n+1)]
NODE_RANGE[n] = [A[n], A[n]]
NODE_MAX = [0 for i in range(n+1)]
NODE_MAX[0]=1

for i in range(n-1, -1, -1):
    node_min = math.ceil( NODE_RANGE[i+1][0]/2 ) + A[i]
    node_max = NODE_RANGE[i+1][1] + A[i]
    NODE_RANGE[i]=[node_min, node_max]

if NODE_RANGE[0][0] > 1 or 1 > NODE_RANGE[0][1]: 
    print(-1)
    sys.exit()



for i in range(1, n+1):
    NODE_MAX[i] = min((NODE_MAX[i-1]-A[i-1])*2, NODE_RANGE[i][1])
    

print(sum(NODE_MAX))

Solution (Python):



def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if 0 < A[0]:
        return '1' if n == 0 and A[0] == 1 else '-1'

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

    prev = 0
    ret = 0
    for i in range(n, -1, -1):
        if R[i] < A[i]:
            ret = -1
            break

        prev = min(R[i], A[i]+prev)
        ret += prev

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):







def Csum(a):
    b,c=[],0
    for i in range(len(a)):
        c+=a[i]
        b.append(c)
    return b








n=int(input())
a=list(map(int,input().split()))
s,su,b,c=Csum(a),sum(a),1,0
for i in range(n+1):
    
    
    c+=b
    b-=a[i]
    
    
    if b<=0:
        if i==n and b==0:
            print(c)
        else:
            print(-1)
        break
    
    
    b=min(b*2,su-s[i])

Solution (Python):

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


NowNode = 2**0
NextNode = (NowNode - A[0])*2
UpperLimit = [0] * (N+1)
UpperLimit[0] = 1
if A[0] == 1:
    if N == 0:
        print(1)
        exit()
    print(-1)
    exit()
for d in range(1, N+1, 1):
    NowNode = NextNode
    NextNode = (NowNode - A[d]) * 2
    UpperLimit[d] = NowNode

UpperLimit[-1] = min(A[-1], UpperLimit[-1])

NowNode = A[-1]
ans = 0

for d in range(N, -1, -1):
    PrevNode = NowNode
    if UpperLimit[d] < A[d]:
        print(-1)
        exit()
    if NowNode + A[d] <= UpperLimit[d]:
        NowNode += A[d]
    else:
        NowNode = UpperLimit[d]
    ans += NowNode
    
print(ans)

Solution (Python):
def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    
    rem=sum(L)
    cur=1
    ans=0
    for i in range(n+1):
        ans+=cur
        rem-=L[i]
        cur-=L[i]
        if cur<0 or cur==0 and i!=n:
            print(-1)
            return
        if cur<rem:
            cur=min(cur*2,rem)
            
    print(ans)

if '__main__' == __name__:
    main()

Solution (Python):









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

    if N > 0 and As[0] != 0:
        return -1
    if N == 0 and As[0] != 1:
        return -1        

    vertices = [1] * (N+1)
    previous = 0
    for i, a in enumerate(As[:0:-1]):
        max_n_vert = a + previous
        previous = max_n_vert
        vertices[N-i] = max_n_vert

    n_not_leaves_prev = 1
    for i, a in enumerate(As):
        if i == 0:
            continue
        
        

        max_n_vert = 2 * n_not_leaves_prev
        vertices[i] = min(vertices[i], max_n_vert)
        n_not_leaves_prev = vertices[i] - a

        if max_n_vert < a:
            return -1

    return sum(vertices)


def main():
    print(solve())


if __name__ == "__main__":
    main()

Solution (Python):
import math


def main():
    depth = int(input())
    leaves = [int(x) for x in input().split()]

    nodes_range = [None] * (depth + 1)
    for i in range(depth, -1, -1):
        if i == depth:
            nodes_range[i] = (leaves[i], leaves[i])
            continue
        
        min_nodes = math.ceil(nodes_range[i + 1][0] / 2) + leaves[i]
        
        max_nodes = nodes_range[i + 1][1] + leaves[i]
        nodes_range[i] = (min_nodes, max_nodes)

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

    max_noded_tree = [0] * (depth + 1)
    for i in range(depth + 1):
        if i == 0:
            max_noded_tree[i] = 1
            continue
        max_noded_tree[i] = min(
            (max_noded_tree[i - 1] - leaves[i - 1]) * 2,
            nodes_range[i][1])
    print(sum(max_noded_tree))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n = ni()
    a = nl()
    ok = -1
    ng = 10**18
    ans = -1
    while ng - ok > 1:
        v = mid = (ok + ng) // 2
        c = 0
        cnt = 0
        for x in a[:0:-1]:
            cnt += c + x
            c += x
            d = (c - 1) // 2 + 1
            if v > c - d:
                v -= c - d
                d = c
            elif v > 0:
                d += v
                v = 0
            c = d
        if a[0] + c > 1:
            ng = mid
        else:
            ok = mid
            ans = cnt + 1
    print(ans)
    return

solve()

Solution (Python):
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A=map(int,read().split())

bound = [0]*(N+1)
bound[0] = 1

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


for i in range(1,N+1):
  bound[i] = (bound[i-1]-A[i-1]) *2
  if bound[i] < A[i]:
    print(-1)
    sys.exit()
    

cum_sum = 0 
for i in range(N,-1,-1):
  cum_sum += A[i]
  bound[i] = min(bound[i],cum_sum)
print(sum(bound))

Solution (Python):
import math


def main():
    depth = int(input())
    leaves = [int(x) for x in input().split()]

    nodes_range = [None] * (depth + 1)
    for i in range(depth, -1, -1):
        if i == depth:
            nodes_range[i] = (leaves[i], leaves[i])
            continue
        min_nodes = math.ceil(nodes_range[i + 1][0] / 2) + leaves[i]
        max_nodes = nodes_range[i + 1][1] + leaves[i]
        nodes_range[i] = (min_nodes, max_nodes)

    if not (nodes_range[0][0] <= 1 <= nodes_range[0][1]):
        
        print(-1)
        return

    max_noded_tree = [0] * (depth + 1)
    for i in range(depth + 1):
        if i == 0:
            max_noded_tree[i] = 1
            continue
        max_noded_tree[i] = min(
            (max_noded_tree[i - 1] - leaves[i - 1]) * 2,
            nodes_range[i][1])
    print(sum(max_noded_tree))
    return


if __name__ == '__main__':
    main()

Solution (Python):


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

ans = 0


ans += 1
currentRootNodeNum = 1
if (leafNums[0] >= 1 and n >=1) or (leafNums[0] > 1 and n == 0):
    print(-1)
    exit()


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


for i in range(1, n+1):
    
    cond2max = leafAccumlateFromEnd[i]
    cond1max = currentRootNodeNum*2
    currentMax = min(cond1max, cond2max)
    ans += currentMax
    currentRootNodeNum = currentMax - leafNums[i]
    if currentRootNodeNum < 0:
        print(-1)
        exit()

print(ans)

Solution (Python):
N,*A = map(int, open(0).read().split())
ans = 0
temp = 0


limit = [0] * (N+1)
if N == 0:
    if A[0] == 1:
        print('1')
    else:
        print('-1')
else:
    if A[0] != 0:
        print('-1')
    else:
        limit[0] = 1
        for i in range(1,N+1):
            limit[i] = (limit[i-1]*2) - A[i]
            if limit[i] < 0:
                print('-1')
                break
            elif limit[i] == 0:
                if i < N:
                    print('-1')
                    break
        else:
            for i in range(N+1):
                if i == 0:
                    temp = A[N]
                    ans += temp
                    lower = temp
                elif i < N:
                    temp = min(lower,limit[N-i]) + A[N-i]
                    ans += temp
                    lower = temp
                else:
                    ans += 1
            else:
                print(ans)

Solution (Python):
import sys
from functools import lru_cache
 

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n=read()
a=list(reads())
if a[0]>1:
  print("-1")
  exit()
res=0
node=[0 for _ in range(n+1)]
node[-1]=a[-1]


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

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


for i in range(n+1):
  if node[i]<a[i]:
    print("-1")
    exit()
  if (node[i]<=0 and i<n) :
    print("-1")
    exit()
  res+=node[i]
print(res)

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

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

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


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(sum(lis)+sum(sup))

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


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=1

for i in range(1,n+1):
    w=min(w*2,v[i][1])
    ans+=w
    
    w-=a[i]
print(ans)

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

if N == 0 and A[0] != 1:                            
    ans = -1
elif N != 0 and A[0] != 0:                          
    ans = -1
else:
    ans = 1                                         
    node = 1                                        
    lateFolia = sum(A)                              
    preFolia = 0                                    

    for d in range(1, N+1):                         
        folia = A[d]                                
        node = min((node-preFolia)*2, lateFolia)    
                                                    
                                                    

        if node < folia:                            
            ans = -1
            break

        ans += node                                 
        lateFolia -= folia                          
        preFolia = folia                            

print(ans)

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

if N == 0 and A[0] != 1:                            
    ans = -1
elif N != 0 and A[0] != 0:                          
    ans = -1
else:
    ans = 1                                         
    node = 1                                        
    lateFolia = sum(A)                              
    preFolia = 0                                    

    for d in range(1, N+1):                         
        folia = A[d]                                
        node = min((node-preFolia)*2, lateFolia)    

        if node < folia:                            
            ans = -1
            break

        ans += node                                 
        lateFolia -= folia                          
        preFolia = folia                            

print(ans)

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