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()))
if n==0:
    if a[0]==1:
        print(1)
    else:
        print(-1)
    exit()
ma = [None]*n
ma[0] = 1
for i in range(n-1):
    ma[i+1] = (ma[i]-a[i])*2
node = a[-1]
ans = node
for i in range(n-1, -1, -1):
    mi = (node+1)//2
    if ma[i]-a[i]<mi:
        print(-1)
        exit()
    node = min(ma[i]-a[i], node) + a[i]
    ans += node
print(ans)

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    from itertools import islice
    cap = [1]
    for a in A:
        cap.append(2*(cap[-1]-a))
    ans = 0
    p = 0
    for a, c in zip(A[N::-1], cap[N::-1]):
        c -= a
        if 2 * c < p:
            return -1
        p = min(c, p) + a
        ans += p
    return ans


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)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    cur = 1
    ret = 0
    t = []
    for i in range(N):
        v = A[i]
        if v >= cur:
            print(-1)
            return
        t.append(cur)
        ret += cur
        
        cur = (cur - v) * 2
    if A[-1] > cur:
        print(-1)
        return
    ret += A[-1]
    

    mx = A[-1]
    for i in range(1, N)[::-1]:
        tmp = min(mx + A[i], 2 ** i)
        if t[i] > tmp:
            ret -= t[i] - tmp
        
        mx = min(tmp, 2 ** (i - 1))
    print(ret)
    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()))
node=[1 for _ in range(N+1)]
Sn=sum(A)
S=[Sn]
for s in range(N):
    S.append(S[s]-A[s+1])

ans=1
for i in range(1,N+1):
    if node[i-1]*2<=S[i-1]:
        ans+=node[i-1]*2
        node[i]=node[i-1]*2
    elif node[i-1]<=S[i-1]<node[i-1]*2:
        node[i]=S[i-1]
        ans+=S[i-1]
    node[i]-=A[i]
    if node[i]<0:
        ans=-1
        break

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

print(ans)

Solution (Python):
n=int(input())
alist = list(map(int, input().split()))
gokei=sum(alist)
nokori=gokei

if alist[0]!=0:
    if n==0 and alist[0]==1:
        print(1)
    else:
        print(-1)
else:
    oya=1
    answer=1
    ng=0
    for i in range(n-1):
        
        if alist[i+1]>oya*2:
            ng=1
        oya=min(oya*2-alist[i+1], nokori-alist[i+1])
        answer+=oya
        answer+=alist[i+1]
        nokori-=alist[i+1]
        
    
    if alist[-1]>oya*2:
        ng=1
        
    answer+=alist[-1]
    
    if ng==1:
        print(-1)
    else:
        print(answer)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
r = 1
maxi = [0] * (n + 1)

ok = True

for i in range(n + 1):
    if r <= 0 or a[i] > r:
        ok = False
        break
    maxi[i] = r
    r = 2 * (r - a[i])

branches = a[n]
ans = a[n]
for i in range(n - 1, -1, -1):
    branches = min(branches + a[i], maxi[i])
    ans += branches

if not ok:
    ans = -1

print(ans)

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

next_max_node = 1

for leaf in a:
    if leaf > next_max_node:
        print(-1)
        exit()
    next_max_node = (next_max_node - leaf) * 2

num_sum = 0

for i in range(1, n+2):
    tmp = a[-i]
    b[-i] = a[-i] + num_sum
    num_sum += a[-i]

ret = 0
next_max_node = 1

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

print(ret)

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


if A[0] == 1:
  if N == 0:
    print("1")
  else:
    print("-1")
  quit()
elif A[0] > 1:
  print("-1")
  quit()
  
answer = 0
ans = [0] * (N + 1)
ans2 = [0] * (N + 1)
now = 1
ans[0] = 1
ans2[N] = A[-1]

for i in range(N):
  if now >= A[i]:
    now = 2 * (now - A[i])
    ans[i + 1] += now
  else:
    print("-1")
    quit()

if now < A[-1]:
  print("-1")
  quit()
  
for i in range(1, N + 1):
  ans2[N - i] = ans2[N - i + 1] + A[N - i]

for i in range(N + 1):
  answer += min(ans[i], ans2[i])
  


print(answer)

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

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


leaf = []
miki = []
under = 1

for i, a in enumerate(A):
    if a > under:
        print(-1)
        exit()
    miki.append(under - a)
    under = miki[-1] * 2


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

print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
AA=[0]
for a in A[1:]:
    AA.append(AA[-1]+a)
f=1 if A[0]==0 or N==0 and A[0]==1 else 0
r=1
b=1
for i,a in enumerate(A[1:]):
    x=min(b*2,AA[-1]-AA[i])
    if i<N-1 and x>a or i==N-1 and x==a:
        b=x-a
        r+=x
    else:
        f=0
print(r if f else -1)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
flag = True
pos = [[1,1] for _ in range(n+2)]
for i in range(n+1):
    if pos[i][1] < a[i]:
        flag = False
    pos[i+1][0] = max(0,pos[i][0]-a[i])
    pos[i+1][1] = (pos[i][1]-a[i])*2
ans = a[n]
cur = a[n]
for i in range(n)[::-1]:
    cur = min(cur+a[i],pos[i][1])
    ans += cur
if flag:
    print(ans)
else:
    print(-1)

Solution (Python):
def solve():
    n = int(input())
    av = list(map(int, input().split(' ')))
    cur = 1
    ans = 0
    s = sum(av)
    for i in range(n+1):
        if cur < av[i]: return -1
        ans += cur
        s -= av[i]
        cur -= av[i]
        if (s <= cur * 2):
            j = 1
            while i + j < n + 1:
                ans += j * av[i + j]
                j += 1
            break
        cur *= 2
    return ans

print(solve())

Solution (Python):
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))



N=int(input())
A=nl()

Hsum=sum(A)
Ntop=1
topnow=1

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

if(A[0]==1):
    if(N==0):
        print(1)
        sys.exit(0)
    else:
        print(-1)
        sys.exit(0)
    
for i in range(1,len(A)):
    if(topnow*2<=Hsum):
        topnow=topnow*2-A[i]
        if(topnow<0):
            print(-1)
            sys.exit(0)
        Hsum-=A[i]
        Ntop+=topnow+A[i]
    else:
        topnow=Hsum
        Ntop+=Hsum
        Hsum-=A[i]

print(Ntop)

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

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

for i in range(N-1,-1,-1):
    C[i] = C[i+1]+A[i]
    
check = 0
D = [0]*(N+1)

for i in range(N+1):
    if A[i]>B[i]:
        check += 1
    D[i] = min(B[i],C[i])
    
if N==0:
    if A[0]!=1:
        check += 1

if check == 0:
    print(sum(D))
else:
    print("-1")

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



m = [1]

flag = True

for i in range(n+1):
    if m[i] < a[i]:
        flag = False
        break
    elif i < n:
        m.append((m[i] - a[i]) * 2)



s = 0

if not flag:
    s = -1

else:
    u = 0

    for i in reversed(range(n+1)):
        s += min(a[i] + u, m[i])
        u += a[i]

print(s)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    x = 2 ** N
    c = 1

    past = [0]
    for i, a in enumerate(A):
        if a > c:
            print(-1)
            return
        elif a == 0:
            past.append(c)
            c *= 2
        else:
            past.append(c)
            c = (c - a) * 2

    ans = 0
    c = 0
    
    for i, p in enumerate(past[::-1]):
        if i == N + 1:
            continue
        ans += min(c + A[-1 -i], p)
        c += A[-i - 1]


    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def solve():
    n = II()
    a = LI()
    ma = [None] * (n + 1)
    tmp = 0
    for i in range(n, -1, -1):
        x = pow(2, i)
        tmp += a[i]
        if tmp <= x:
            tmp = (tmp - 1) // 2 + 1
            continue
        else:
            print(-1)
            return
    ma[n] = a[-1]
    for i in range(n - 1, -1, -1):
        ma[i] = min(pow(2, i), ma[i + 1] + a[i])
    tmp = 1
    ans = 1
    for i in range(1, n + 1):
        tmp = tmp * 2
        ans += min(tmp, ma[i])
        tmp = min(tmp, ma[i])
        tmp -= a[i]
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
n=int(input())
n+=1
a=list(map(int,input().split()))
nokori=[0]*n

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

kazu=[0]*n
kazu[0]=1
kano=True

for i in range(1,n):
    active=kazu[i-1]-a[i-1]
    if(active<=0):
        kano=False
        
        break
    kazu[i]=min(active*2,nokori[i])

if(kazu[n-1]!=a[n-1]):
    kano=False

if(kano):
    print(sum(kazu))
else:
    print(-1)

Solution (Python):
import sys


def print_(ans):
    print(ans)
    sys.exit()


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split(' ')))
    if n == 0:
        if a[0] == 1:
            print_(1)
        else:
            print_(-1)
    if a[0] != 0:
        print_(-1)
    max_rest = [0 for _ in range(n + 1)]
    max_rest[0] = 1 - a[0]
    for i in range(1, n + 1):
        max_rest[i] = max_rest[i - 1] * 2 - a[i]
    for i in range(n + 1):
        if max_rest[i] < 0:
            print_(-1)
    rest = [0 for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        req_rest = (a[i + 1] + rest[i + 1] + 1) // 2
        if max_rest[i] < req_rest:
            print_(-1)
        rest[i] = min(max_rest[i], a[i + 1] + rest[i + 1])
    ans = sum(a) + sum(rest)
    print_(ans)

Solution (Python):
def f(N, A):
    B = [0]*(N+1)
    b = 0
    for i in range(N, -1, -1):
        b += A[i]
        B[i] = b


    x = 1
    s = 0

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

    return s


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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
can_root=1
ls=[1]
for i in range(n):
    if can_root<a[i]:
        print(-1);exit()
    can_root=(can_root-a[i])*2
    ls.append(can_root)
if can_root < a[-1]:print(-1);exit()
ans=a[-1]
start=a[-1]
for i in range(n)[::-1]:
    start+=a[i]
    ans+=min(ls[i],start)
print(ans)

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

cAs = list(accumulate(As[::-1]))[::-1][1:] + [0]

ans = 0
now_nodes = 1
for i, (cum, a) in enumerate(zip(cAs, As)):
    if i==N:
        if now_nodes==a:
            print(ans+a)
        else:
            print(-1)
    if now_nodes<=a and i!=N:
        print(-1)
        break
    num = min(cum, (now_nodes-a)*2)
    ans += now_nodes
    now_nodes = num

Solution (Python):
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

M = [tuple() for _ in range(N + 1)]
for i, a in enumerate(reversed(A)):
    i = N - i
    if i == N:
        M[i] = (a, a)
    else:
        n, m = M[i + 1]
        M[i] = (-(-n // 2) + a, m + a)

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

ans = 1
par = 1
for i in range(1, N + 1):
    least, most = par, par * 2
    minv, maxv = M[i]
    v = min(maxv, most)
    ans += v
    par = v - A[i]
print(ans)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = []
    now = 1
    ans = 0
    for i in range(n+1):
        if a[i] > now:
            print(-1)
            return
        else:
            dp.append(now)
            now -= a[i]
            now *= 2
    now = 0
    for i in range(n, -1, -1):
        now += a[i]
        ans += min(now, dp[i])
    print(ans)


main()

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

    tot = sum(A)

    ans = 1
    tot -= 1
    v = 1
    for x in A:
        v -= x
        if v < 0:
            print(-1)
            return
        make_v = min(v, tot)
        tot -= make_v
        v += make_v
        ans += v

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
yuyo = [0] * (N + 1)
nokori = [0] * (N + 2)
A.append(0)
nokori[N + 1] = 0
ans = 0
for i in range(N,-1,-1):
    nokori[i] = nokori[i + 1] + A[i + 1]
ans = 0
if A[0] != 0:
    if A[0] == 1 and N == 0:
        ans = 1
    else:
        ans = -1
else:
    yuyo[0] = 1
    for i in range(1,N + 1):
        yuyo[i] = min(yuyo[i - 1] * 2 - A[i],nokori[i])
        if yuyo[i] < 0:
            ans = -1
            break
if ans == -1:
    print(-1)
else:
    for i in range(N):
        ans += yuyo[i]
    ans += nokori[0]
    print(ans)

Solution (Python):
N = int(input())
A = [0]+list(map(int, input().split()))
ans = 0
tree = []
presum = 0
for i, elt in enumerate(A[:0:-1]):
    presum += elt
    tree += presum,
vertices = []
last = .5
for i,elt in enumerate(tree[::-1]):
    last = min(2*(last-A[i]), elt)
    ans += int(last)
    if last <= 0:
        break
if last > 0 and last == A[-1]:
    print(ans)
else:
    print(-1)

Solution (Python):
n = int(input())
num = [int(i) for i in input().split()]

count = 1
vertexCount = 0
rem = sum(num)
for m in num:
    vertexCount += count
    count -= m
    rem -= m
    if count < 0:
        vertexCount = -1
        break
    count = min(count*2, rem)

print(vertexCount)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations, accumulate
from bisect import bisect_left, bisect_right  














N = read_a_int()
A = read_ints()


n_leaves_under = list(reversed(list(accumulate(reversed(A))))) + [0]






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

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
def pow2(a):
    return 1<<min(a, 63)
ans = 0
Cap = []
c = 1
for d, a in enumerate(A):
    Cap.append(c)
    c -= a
    if c < 0:
        print(-1)
        exit()
    c *= 2
    if c >= 1<<63:
        c = 1<<63
siz = 0

for d, a, cap in zip(range(N, -1, -1), A[::-1], Cap[::-1]):
    
    siz = min(siz+a, cap)
    ans += siz
    
print(ans)

Solution (Python):


import sys






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def make_top_constraints(n, L):
        top_c = [tuple() for _ in range(n+1)]
        top_c[0] = (1, 1)    
        for i in range(1, n+1):
            
            minimum = max(top_c[i-1][0] - L[i-1], 0)    
            
            maximum = max((top_c[i-1][1] - L[i-1]) * 2, 0)
            top_c[i] = (minimum, maximum)
        return top_c


    def make_bottom_constraints(n, L):
        bottom_c = [tuple() for _ in range(n+1)]
        bottom_c[n] = (L[n], L[n])    
        for i in range(n-1, -1, -1):
            
            minimum = bottom_c[i+1][0] // 2 + L[i]
            
            maximum = bottom_c[i+1][1] + L[i]
            bottom_c[i] = (minimum, maximum)
        return bottom_c


    def max_cross_num(L1, L2):
        left = max(L1[0], L2[0])
        right = min(L1[1], L2[1])
        if left > right:
            return -1
        else:
            return right


    def calc_max_node(n, top_down_constraints, bottom_up_constraints):
        cnt = 0
        for i in range(n+1):
            num = max_cross_num(top_down_constraints[i], bottom_up_constraints[i])
            
            if num < 0:
                return -1
            cnt += num
        return cnt
    
    
    n = ii()
    L = lmi()

    
    top_down_constraints = make_top_constraints(n, L)
    
    bottom_up_constraints = make_bottom_constraints(n, L)

    
    

    print(calc_max_node(n, top_down_constraints, bottom_up_constraints))


if __name__ == "__main__":
    main()

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

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

max_e = sum(a)
if(max_e > 2**n):
    print(-1)
    exit()

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

for i,leaf in enumerate(a):
    if(i==0):
        continue

    not_leaf[i] = min(not_leaf[i-1]*2, max_e) - leaf
    if(not_leaf[i] < 0):
        print(-1)
        exit()
    max_e -= leaf

ans = sum(a) + sum(not_leaf)
print(ans)

Solution (Python):
import math
import sys
a=int(input())
List=list(map(int,input().split()))
s=sum(List)
r=1
count=0
for i in range(a+1):
  count+=r
  r-=List[i]
  s-=List[i]
  if r<0:
    print(-1)
    sys.exit()
  r=min(s,2*r)
print(count)

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):
import sys
input = sys.stdin.readline

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

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

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

NODE=[0]*(N+5)
NODE[0]=1
rest=1
ANS=0
ind=0

for i in range(N+1):
    
    if A[i]>rest:
        print(-1)
        sys.exit()

    else:
        x=A[i]
        while x:
            if NODE[ind]<=x:
                ANS+=(i-ind+1)*NODE[ind]
                x-=NODE[ind]
                rest-=NODE[ind]
                NODE[ind]=0
                ind+=1
            else:
                ANS+=(i-ind+1)*x
                NODE[ind]-=x
                rest-=x
                x=0

        NODE[i+1]=rest
        rest*=2
        if rest>10**20:
            rest=10**20

print(ANS)

Solution (Python):
import sys
N = int(input())
A = list(map(int, input().split()))
C = []
t = 0
for i in range(N, -1, -1):
    t += A[i]
    C.append(t)
C = C[::-1]

zanki = 1
ans = 1
for i in range(N+1):
    zanki -= A[i]
    if zanki < 0:
        print(-1)
        sys.exit()
    if zanki == 0 and i != N:
        print(-1)
        sys.exit()
    zanki *= 2
    if i < N and zanki >= C[i+1]:
        zanki = C[i+1]
    ans += zanki
print(ans)

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

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

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

ret = a[-1]
suc = a[-1]
for i_ in range(n):
    i = n-1-i_
    ret += min(suc,par[i]) + a[i]
    suc = min(suc,par[i]) + a[i]

print(ret)

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

n = int(input())
a = [int(i) for i in input().split()]
maxNode = 1
total = 0
b = a[:]
for i in range(n, 0, -1):
	b[i - 1] += b[i]
for i in range(n + 1):
	maxNode = min(maxNode, b[i])
	if maxNode == 0 or maxNode < a[i]:
		print(-1)
		exit(0)
	total += maxNode
	maxNode = (maxNode - a[i]) * 2 
print(total)

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

bunki=sum(A)-1

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

for i in range(N):
    if bunki>0:
        bunki_use=min(bunki,ans[i]-A[i])
        bunki-=bunki_use
        ans[i+1]=ans[i]+bunki_use-A[i]
    else:
        ans[i+1]=ans[i]-A[i]

    if ans[i+1]<1:
        print(-1)
        exit()

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

print(sum(ans))

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

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

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

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

now = 1
allows = []
for i in range(n):
    ha = a[i]
    if ha > now:
        print(-1)
        exit()
    allows.append(now - ha)
    now = (now - ha) * 2
if now < a[n]:
    print(-1)
    exit()
result = a[n]
now = a[n]
for i in range(n):
    if now > allows[n-1-i]:
        now = allows[n-1-i]
    now = now + a[n-1-i]
    result += now
print(result)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    
    return 1/f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def solve():
    n = getN()
    nums = getList()
    
    if n == 0:
        if nums[0] == 1:
            print(1)
        else:
            print(-1)
        return
    
    if nums[0] > 0:
        print(-1)
        return

    acc = []
    tmp = 0
    for i , num in enumerate(nums[::-1]):
        tmp += num
        acc.append(tmp)
    acc.reverse()

    ans = 1
    ue = 1
    for i, num in enumerate(nums[1:-1]):
        if ue * 2 <= num:
            print(-1)
            return
        konodan = min(ue * 2, acc[i+1])
        
        ans += konodan
        ue = konodan - num

    if ue * 2 < nums[-1]:
        print(-1)
        return

    print(ans + nums[-1])
    return


def main():
    
    
    solve()
if __name__ == "__main__":
    solve()

"""
    12
    3 2
    3 2
    0 1
    2 -1
    -3 -9
    -8 12
    7 0
    8 1
    8 2
    8 4
    0 0
    0 0
"""

Solution (Python):
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json

import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    
    
    A = [int(a) for a in input().split()]
    

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

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

    s = []
    t = 0
    for a in reversed(A):
        s.append(t)
        t += a
    s = list(reversed(s))

    res = 1
    nodes = 1

    for i in range(1, N + 1):
        max_nodes = nodes * 2
        nokori = s[i]
        leafs = A[i]
        if leafs > max_nodes:
            print(-1)
            return
        not_leafs = min(max_nodes - leafs, nokori)
        res += not_leafs + leafs
        nodes = not_leafs
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [int(hoge) for hoge in input().split()]
nodemax = []
cur = 0
for a in reversed(A):
    cur += a
    nodemax.append(cur)
nodemax = list(reversed(nodemax))
ans = 1
curnode = 1
for n,a in enumerate(A):
    
    nothappa = curnode - A[n]
    if n!=N:
        if nothappa <= 0:
            ans = -1
            break
        else:
            nextnode = min(nodemax[n+1],nothappa*2)
            ans += nextnode
            curnode = nextnode
    else:
        if nothappa !=0:
            ans = -1
print(ans)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    s = sum(A)

    if n == 0:
        print(1 if A[0] == 1 else -1)
        return

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

    not_leaf = 1
    
    for d in range(n + 1):
        if not_leaf < A[d]:
            print(-1)
            return
        not_leaf -= A[d]
        not_leaf *= 2

    res = 0
    not_leaf = 1
    count = 1 
    for d in range(n + 1):
        not_leaf -= A[d]
        
        add = min(s - count, not_leaf)
        count += add
        not_leaf += add
        res += not_leaf
        

    print(res + 1)
resolve()

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()

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

    m = [1] * (N + 1)
    m[-1] = A[-1]
    for i in range(N, 0, -1):
        m[i - 1] = (m[i] + 1) // 2 + A[i - 1]
    
    res = 0
    t = 0
    for i in range(N, -1, -1):
        if M[i] <= 0:
            print(-1)
            return

        t = min(t + A[i], M[i])
        if t < m[i]:
            print(-1)
            return

        res += t

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
l=[0]*(N+1)
l[-1]=A[-1]
for i in range(N-1,0,-1):
    l[i]=A[i]+l[i+1]
t=1
a=1
ma=10**15
for i in range(1,N+1):
    if 2*t<A[i]:
        a=-1
        break
    t=min(t*2,l[i])
    a+=t
    t-=A[i]
if A[0]!=0:
    a=-1
if N==0 and A[0]==1:
    a=1
print(a)

Solution (Python):
d,l = [list(map(int, s.split())) for s in open(0)]
d = d[0]

ans = 0
v_max = [1]
for i in range(d+1):
    if v_max[i] - l[i] < 0:
        ans = -1
        break
    v_max.append((v_max[i] - l[i])*2)
else:
    _max = 0
    for i in range(d, -1, -1):
        _max = min(_max + l[i], v_max[i])
        ans += _max
print(ans)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	N = int(input())
	A = getlist()
	Lmin = [0] * (N + 1)
	Lmax = [0] * (N + 1)
	Lmin[-1] = A[-1]
	Lmax[-1] = A[-1]
	for i in range(N - 1, -1, -1):
		if Lmin[i + 1] % 2 == 0:
			Lmin[i] = A[i] + int(Lmin[i + 1] // 2)
		else:
			Lmin[i] = A[i] + int(Lmin[i + 1] // 2) + 1
		
		Lmax[i] = Lmax[i + 1] + A[i]

	
	

	if Lmin[0] > 1:
		print(-1)
		return

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

	
	print(sum(Node))


if __name__ == '__main__':
	main()

Solution (Python):
from sys import exit

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

sm = sum(a)
ans = 1

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

if a[0] != 0 or a[n] == 0:
  print(-1)
  exit()
  
s = 1
for i in range(1, n+1):
  if a[i] > s * 2:
    print(-1)
    exit()
  s = min(s*2, sm)
  ans += s
  sm -= a[i]
  s -= a[i]
  
print(ans)