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

ans = 0

parents = 1

if n == 0:
    if a[0] > 1:
        ans = -1
    else:
        ans = a[0]

if a[0] == 1:
    parents = 0
    ans = 1
    if n != 0:
        ans = -1

parentsls = [0 for _ in range(n+1)]
parentsls[0] = parents

bicapls = [0 for _ in range(n+1)]

for i in range(1, n+1):
    if i != n and parents == 0:
        ans = -1    
        break
    if a[i] > parents*2:
        ans = -1
        break
    else:
        parents = parents*2 - a[i]
        parentsls[i] = parents
    
if ans != -1 and ans != 1:
    node = 0
    for i in range(n):
        if parentsls[n-1-i] >= node + a[n-i]:
            ans += node + a[n-i]
            node = node + a[n-i]
        else:
            ans += node + a[n-i]
            node = parentsls[n-1-i]

    ans += 1

print(ans)

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

b = [1]
for i in range(n):
    tmp = b[i] - a[i]
    b.append(min(tmp * 2, a_min[i + 1]))
    if tmp < 1:
        print(-1)
        break
else:
    if b[n] != a[n]:
        print(-1)
    else:
        print(sum(b))

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

pm = sum(A)
e = 1
te = 1
for i in A:
    pm -= i
    e = min((e-i) * 2,pm)
    if e < 0:
        break
    te += e
if e < 0:
    print(-1)
else:
    print(te)

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


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

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

suma=sum(a)

cnt=1
bk=1

for i,aa in enumerate(a[1:]):
    node=min(suma,bk*2)
    cnt+=node
    
    bk=node-aa
    suma-=aa

if bk==0:
    print(cnt)
else:
    print(-1)

Solution (Python):


n=int(input())
a=list(map(int,input().split()))
s=sum(a)-1
ans,x=0,1

for i in range(n):
  if a[i]>x-1:
    print(-1)
    exit()
  ans+=x
  x-=a[i]
  if i<n-1 and x<=0:
    print(-1)
    exit()
  if s>=0:
    if s>=x:
      s-=x
      x=x*2
    else:
      x=(x-s)+s*2
      s=0
if x!=a[-1] or x<=0:
  print(-1)
  exit()
ans+=x
print(ans)

Solution (Python):
n,*a=map(int,open(0).read().split())
A=sum(a)
ans=1
now=1
for i in a:
    A-=i
    now=min((now-i)*2,A)
    ans+=now
    if now<0:
        print(-1)
        exit()
print(ans)

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


branches = dict()
for idx,a in enumerate(A):
  if idx == 0:
    branch = 1-a
  else:
    branch = branch * 2 - a
  if branch <0:
    print(-1)
    quit()
  branches[idx] = branch


ans =0 
for idx,leaf in enumerate(reversed(A)):
  if idx == 0:
    nodes = leaf
  else:
    if branches[len(A)-idx-1] <nodes//2:
      print(-1)
      break
    nodes = min(
      leaf + nodes,
      leaf + branches[len(A)-idx-1]
    )
  ans += nodes
else:
  print(ans)

Solution (Python):


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

if a == 0 and A[0] == 1:
    print(1)
    exit()
ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    







cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]

if 0 in cH:
    print(-1)
    exit()
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:]):
    
    if n//2+(n%2!=0)>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        
        ans += n+i
        n+=i
    else:
        
        ans +=cH[e]+i
        n = cH[e]+i

    
print(ans)

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

nodes = [0] * (N + 1)
nodes[0] = 1 - A[0]

if N == 0 and A[0] > 1:
    print(-1)
else:
    for index, a in enumerate(A[1:], start=1):
        nodes[index] = nodes[index - 1] * 2 - a
        if nodes[index] < 0:
            print(-1)
            break
    else:
        fixed_nodes = [0] * (N + 1)
        fixed_nodes[-1] = A[-1]
        for i in reversed(range(N)):
            fixed_nodes[i] = min(nodes[i], fixed_nodes[i + 1]) + A[i]
        if any([n == 0 for n in fixed_nodes]):
            print(-1)
        else:
            print(sum(fixed_nodes))

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

MAX = [P[-1]] * (N+1)
MIN = 0
J = True

for i in range(N):
  MAX[N-1-i] = MAX[N-i] + P[N-1-i]

follow = 1
hikaku = True
ans = 0
for i in range(N+1): 
  p = follow + P[i]
  if follow < 0:
    J = False
  if hikaku:
    if p >= MAX[i]:
      hikaku = False
      ans += MAX[i]
    else:
      ans += p
      follow *= 2
      if i != N:
        follow -= P[i + 1]
      else:
        follow += P[-1]
  else:
    ans += MAX[i]
  
  
if P[0] != 0:
  J = False
  
if N == 0 and P[0] == 1:
  J = True
  
if J:
  print(ans)  
else:
  print(-1)

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

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

nodeM = nodeS[0]-A[0]

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

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


for i in range(N):
    nodeS[i+1] = nodeM*2
    nodeM = nodeS[i+1] - A[i+1]
    if nodeS[i] >= laS[i]:
        j = i
        break
    if i == N-1:
        if nodeS[i+1] >= laS[i+1]:
            j = i+1
        else:
            print(-1)
            exit()

for i in nodeS:
    if i < 0:
        print(-1)
        exit()

ans = sum(nodeS[:j]) + sum(laS[j:])
print(ans)

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

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

node_d = [0 for i in range(n + 1)]


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

node_d[n] = a[n]

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

print(sum(node_d))

Solution (Python):
def main():
    n = int(input())
    line = list(map(int,input().split()))
    if n == 0:
        if line[0] != 1:
            return -1
        else:
            return 1
    if line[0] > 0:
        return -1
    front = [0 for i in range(n+1)]
    back = [0 for i in range(n+1)]
    front[0] = 1
    for i in range(n):
        if front[i] * 2 < line[i+1]:
            return -1
        front[i+1] = min(10**30,front[i]*2-line[i+1])
    back[n] = line[n]
    for i in range(n):
        p = n - i - 1
        back[p] = back[p+1] + line[p]
    ans = 0
    for i in range(n):
        ans += line[i]
        ans += min(front[i],back[i]-line[i])
    ans += line[n]
    return ans


print(main())

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):
n = int(input())
a = [int(x) for x in input().split()]
 
if n == 0:
    print(1 if a[0] == 1 else -1)
    exit()

if a[0] != 0:
    print(-1)
    exit()
 
ans = 1
sm = sum(a)
limit = 1
for i in range(1, n):
    ans += a[i]
    limit = 2*limit - a[i]
    if limit <= 0:
        print(-1)
        exit()
    else:
        sm -= a[i]
        if limit <= sm:
            ans += limit
        else:
            ans += sm

if 2*limit < a[-1]:
    print(-1)
    exit()

ans += a[-1]
 
print(ans)

Solution (Python):


def main():
    N = int( input())
    A = list( map( int, input().split()))
    root = 1
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
        return
    B = A[::-1]
    low = high = B[0]
    
    Hight = [high]
    
    for b in B[1:]:
        low = max(1, (low+1)//2) + b
        high = high + b
        Hight.append(high)
    if low > 1:
        print(-1)
        return
    ans = 1
    now = 1
    BHight = Hight[::-1]
    for i in range(1,N+1):
        if now == 0:
            print(-1)
            return
        h = BHight[i]
        leaf = A[i]
        
        now = min(h, now*2)
        ans += now
        now -= leaf
        if now < 0:
            print(-1)
        
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):


def main():
    N = int( input())
    A = list( map( int, input().split()))
    root = 1
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
        return
    B = A[::-1]
    low = high = B[0]
    
    Hight = [high]
    
    for b in B[1:]:
        low = max(1, (low+1)//2) + b
        high = high + b
        Hight.append(high)
    if low > 1:
        print(-1)
        return
    ans = 1
    now = 1
    BHight = Hight[::-1]
    for i in range(1,N+1):
        h = BHight[i]
        leaf = A[i]
        
        now = min(h, now*2)
        ans += now
        now -= leaf
        
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys

n=int(input())
A=list(map(int,input().split()))
now=1
s=sum(A)
ans=1
if n==0:
    if A[0]!=1:
        print(-1)
    else:
        print(1)
    sys.exit()
if A[0]!=0:
    print(-1)
    sys.exit()
for i in range(1,n+1):
    if A[i]>2*now:
        print(-1)
        sys.exit()
    if s>=2*now:
        ans+=2*now
        now=2*now-A[i]

    else:
        ans+=s
        now=s-A[i]
    s-=A[i]
print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
total = []
num = 0
for i in reversed(range(N+1)):
    num += A[i]
    total.append(num)
total.reverse()
if A[0] == 1 and N == 0:
    print(1)
    exit()
if A[0] != 0:
    print(-1)
    exit()
ans = 1
num = 1
for i in range(1,N+1):
    num = min(2*num, total[i])
    ans += num
    num -= A[i]
    if num < 0:
        print(-1)
        exit()
print(ans)

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

b = [1]
for i in range(n):
    tmp = b[i] - a[i]
    b.append(min(tmp * 2, a_min[i + 1]))
    if tmp < 1 or tmp * 2 < a[i + 1]:
        print(-1)
        break
else:
    if n == 0:
        ans = 1 if a[0] == 1 else -1
        print(ans)
    else:
        print(sum(b))

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








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


if tree[-1] < a_l[-1]:
    print(-1)
    exit()


tree[-1] = a_l[-1]
for i in range(2,n+2):
    
    if tree[-i] == tree[-(i-1)] + a_l[-i]:
        break
    else:
        tree[-i] = min(tree[-i], tree[-(i-1)] + a_l[-i])
    












ans = 0
for val in tree:
    ans += val
print(ans)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline

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

c = 1
ans = 1

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


A = A[::-1]

cnt = A[0]
c = A[0]

can = [A[0]]

for i in range(1, N + 1):
    c += A[i]

    if c > 2**(N - i):
        c = 2**(N - i)

    cnt += c
    can.append(c)

can = can[::-1]
A = A[::-1]

for i in range(1, N + 1):
    if can[i] > (can[i - 1] - A[i - 1]) * 2:
        can[i] = (can[i - 1] - A[i - 1]) * 2

print(sum(can) if A[-1] == can[-1] else -1)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 100

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

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



ok = [1]
for i in range(1, n + 1):
    t = ok[i - 1] * 2 - A[i]
    if i < n and t <= 0:
        print(-1)
        exit()
    ok.append(min(t, MAX))

if ok[n] < 0:
    print(-1)
    exit()

ans = [0] * (n + 1)

ans[n] = A[n]

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


print(sum(ans))

Solution (Python):

N = int(input())
A = list(map(int,input().split()))
leaf= [-1 for i in range(N+1)]
notleaf = [-1 for i in range(N+1)]
flag=0

if N == 0 and A[0] == 1:
    print(1)
elif N==0 and A[0]!=1:
    print(-1)
elif N != 0 and A[0]>=1:
    print(-1)
else:
    leaf[0]=0
    notleaf[0]=1
    for d in range(1, N+1):
        leaf[d] = A[d]
        notleaf[d] = 2*notleaf[d-1] - leaf[d]
        if notleaf[d]<0:
            flag=1
            print(-1)
            break
    if flag == 1:
        pass
    else:
        sleaf = 0
        for i in range(N+1):
            sleaf += leaf[i]
        
        d1 = 0
        for i in range(N+1):
            d1 += (i+1) * leaf[i]
        
        sleaf -= 1
        for i in range(1,N+1):
            if sleaf>0:
                d1 -= i*( min(sleaf, leaf[i]+notleaf[i] - notleaf[i-1]))
                sleaf -= (leaf[i]+notleaf[i] - notleaf[i-1])
            else:
                break
        print(d1)

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

ans = 1
flag = 1

if N == 0:
    if s >= 2:
        flag = 0
    else:
        ans = 1
else:
    for i in range(N):
        e = (e - A[i]) * 2
        if e < A[i+1]:
            flag = 0
            break
        tmp = min(e, s)
        s -= A[i+1]
        ans += tmp
if flag == 0:
    print(-1)
else:
    print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
isOK = True
B = [0]*(N+1)
B[0] = 1-A[0]
M = 1
i = 1
while i <= N:
  B[i] = B[i-1]*2-A[i]
  i += 1
if B[-1] < 0 or N > 0 and A[-1] == 0:
  isOK = False
B[-1] = A[-1]
i = N-1
while i >= 0:
  if B[i] < 1 or i > 0 and B[i] > B[i-1]*2:
    isOK = False
    break
  else:
    B[i] = min(B[i], B[i+1])+A[i]
  i -= 1
print(-1 if not isOK else sum(B))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
edge=[0]*(n+1)
ans=0
edge[0]=1
for i in range(1,n):
    edge[i]=edge[i-1]*2-a[i]
for i in range(n-1,-1,-1):
    bcnt=edge[i+1]+a[i+1]
    if bcnt//2+bcnt%2>edge[i]:
        ans=-1
        break
    if bcnt<edge[i]:
        edge[i]=bcnt
if n==0:
    if a[0]!=1:
        ans=-1
    else:
        edge[0]=0
elif a[0]>0:
    ans=-1
if ans!=-1:
    ans=sum(edge)+sum(a)
print(ans)

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):

    logical_max = [1]
    prev = 1
    for a in A:
        prev = (prev - a)*2
        logical_max.append(prev)
    for l in logical_max:
        if l < 0:
            print(-1)
            return

    logical_max = logical_max[:-1]


    nodes_at_depth = [0] * (N+1)
    d = N
    nodes = 0
    for lg_max, a in zip(logical_max[::-1], A[::-1]):

        nodes += a
        if nodes > lg_max:
            nodes = lg_max
            
        nodes_at_depth[d] = nodes
        d -= 1

    print(sum(nodes_at_depth))

    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()))
t = 1
c = [1-a[0]]+[1]*(n)

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

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

print(sum(a)+sum(c))

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()
if n == 0:
    if a[0] == 1 or a[0] == 0:
        print(1)
        quit()
    else:
        print(-1)
        quit()
for i in range(n):
    if a[i] > 2**i - 1:
        print(-1)
        quit()
if a[-1] > 2**n:
    print(-1)
    quit()

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

i = n-1
tmp = a[-1]
ans = 0
lst2 = [a[-1]]
while i >= 0:
    tmp += a[i]
    tmp = min(tmp, 2**i)
    lst2.append(tmp)
    i -= 1
lst2 = lst2[::-1]
for i in range(n+1):
    ans += min(lst[i], lst2[i])
print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    n_usable_child_list = [0 for _ in range(N + 1)]
    n_usable_child = 1 - A[0]
    for d in range(N):
        n_usable_child_list[d] = n_usable_child
        if n_usable_child < 0:
            print(-1)
            return
        n_usable_child = 2 * n_usable_child - A[d + 1]
    n_usable_child_list[-1] = n_usable_child
    if n_usable_child < 0:
        print(-1)
        return
    ans, cur = 0, 0
    for d in reversed(range(N + 1)):
        cur = min([cur, n_usable_child_list[d]]) + A[d]
        ans += cur
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
n_l = [1]
n = 1
A = [int(a) for a in input().split()]
for i in range(1,N+1):
    a = A[i-1]
    n = (n - a) * 2
    n_l.append(n)
    if n <= 0:
        Good = False
        break
if n >= A[N]:
    counter = A[N]
    m = A[N]
    Good = True
else:
    Good = False
if Good:
    for i in range(N-1,-1,-1):
        n = n_l[i]
        m = min(m+A[i],n)
        counter += m
    print(counter)
else:
    print(-1)

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

if n == 0:
    if l[0] == 1:
        print('1')
        sys.exit()
    else:
        print('-1')
        sys.exit()

if l[0]  != 0:
    print('-1')
    sys.exit()
    
count = 1
edge = 1
sum_ = sum(l)
for i in range(1,len(l)-1):


    sum_ -= l[i]
    
    if l[i] >= edge *2:
        print('-1')
        sys.exit()
    
    if edge * 2 - l[i] <= sum_:
        count += edge * 2
        edge = edge * 2 -l[i]

        continue

        
    if edge * 2 - l[i] > sum_:
        count += sum_ + l[i]
        edge = sum_
        

        continue

        
        

if not   l[len(l)-1] <= edge * 2:
    print('-1')
    sys.exit()
    
else:
    count +=   l[len(l)-1] 
print(count)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
capacity = [1 for k in range(N+1)]
cut = 0
for k in range(N+1):
    
    if A[k] >= capacity[k] and k!= N:
        print(-1)
        break
    if A[k] > capacity[k] and k == N:
        print(-1)
        break
    if k < N:
        capacity[k+1] = 2*(capacity[k] - A[k])
    if k == N:
        ans = [0 for k in range(N+1)]
        ans[0] =1
        sumA = 0
        for m in range(1, N+2):
            sumA += A[-m]
            ans[-m] = min(capacity[-m], sumA)
        print(sum(ans))

Solution (Python):




import math
import sys
import bisect
import heapq  
from collections import deque
inf = 10 ** 15
mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
preoya = 1
arieruoya = [0 for i in range(n+1)]
for i in range(n):
    arieruoya[i] = preoya
    l = a[i]
    if l > preoya*2-1:
        print(-1)
        sys.exit()
    preoya = min((preoya-l)*2,10**13)
if a[n] > preoya:
    print(-1)
    sys.exit()
arieruoya[n] = 0

a.reverse()
premax = a[0]
premin = (a[0]+1)//2
ans=premax
for i in range(1,n+1):
    l = a[i]
    premax = min(arieruoya[n-i], premax+l)
    ans+=premax
print(ans)

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

flag = True
for i in range(n):
    if a[i+1] != 0:
        flag = False
        break

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

nleaf = 1
ans = 0
v = list()

for i in range(n):
    nleaf -= a[i]
    v.append(nleaf)
    nleaf *= 2

if nleaf < a[n]:
    print(-1)
    exit()

nleaf = a[n]
ans += a[n]
for i in range(n-1, -1, -1):
    if v[i]*2 < nleaf:
        print(-1)
        exit()
    if v[i] > nleaf:
        v[i] = nleaf
    nleaf = v[i] + a[i]
    ans += nleaf
print(ans)

Solution (Python):
from collections import defaultdict as dd
import bisect
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
limit = [0] * (n + 1)
total = 0
for i in range(n, -1, -1):
    total += A[i]
    limit[i] = total


"""
for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    

    dp = dd(int)
    mov_dic_keys = set(mov_dic.keys())
    for now_num, total in mov_dic.items():
        mov_dic_keys.remove(now_num)
        for next_num in range(now_num, min(now_num*2 + 1, limit[depth] + 1)):
            if now_num in mov_dic_keys:
                break
            dp[next_num] = max(total + next_num, dp[next_num])
    

if dp[A[-1]] == 0:
    print(-1)
else:
    print(dp[A[-1]])
"""

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

now_num = 1
now_total = 1
for depth in range(n):
    mov_num = now_num - A[depth]
    

    if mov_num > 0:
        now_num = min(mov_num * 2, limit[depth+1])
        now_total += now_num
    else:
        print(-1)
        exit()
if now_num == A[n]:
    print(now_total)
else:
    print(-1)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
node=[1 for _ in range(N+1)] 
S=sum(A) 
ans=1 





for i in range(1,N+1): 
    if node[i-1]*2<=S: 
        ans+=node[i-1]*2
        node[i]=node[i-1]*2
    elif node[i-1]<=S<node[i-1]*2: 
        node[i]=S
        ans+=S
    node[i]-=A[i] 
    S-=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())+1
a = list(map(int, input().split()))
m_node = [1]*n
node = 0
total = 0

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

for i in range(1, n):
    m_node[i] = (m_node[i-1] - a[i-1])*2
    if m_node[i] <= 0:
        print("-1", end="")
        exit()
for i in reversed(range(n)):
    if a[i] > m_node[i]:
        print("-1", end="")
        exit()
    node = min((node+a[i]), m_node[i])
    total += node

print(total, end="")

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
temp=1
summ=0
cont=0
templist=[1]
for i in range(N+1):
  
  if A[i]<temp:
    if i<N:
      summ+=temp
      temp=2*(temp-A[i])
      templist.append(temp)
    elif i==N:
      summ+=temp
      cont+=1
  elif A[i]==temp:
    if i==N:
      summ+=temp
      
      cont+=1
    else:
      print("-1")
      break
  else:
    print("-1")
    break
    
if cont==1:
  if A[N]==temp:
  	print(summ)
  else:
    
    
    comp=A[-1]
    for i in range(N):
      summ-=(templist[-(i+1)]-comp)
      comp+=A[-(i+2)]
      
      
      
      if comp>templist[-(i+2)]:
        print(summ)
        break
      if i==N-1:
        print(summ)
        break

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

num = [0]*(N+1)  

ma = 1
for i, a in enumerate(A):
	if i == N and a <= ma:
		num[i] = ma-a
	elif a <= ma-1:
		num[i] = ma-a
		ma = (ma-a)*2
	else:
		print(-1)
		exit()

tmp = 0
ans = 0
for i, a in enumerate(A[::-1]):
	d = N-i
	if tmp > num[d]:
		tmp = num[d]
	tmp += a
	ans += tmp

print(ans)

Solution (Python):
def solve():
    N = int(input()) + 1
    A = list(map(int, input().split()))

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

    
    MN = [0 for _ in range(N)]
    MN[0] = 1
    for i in range(1, N):
        MN[i] = (MN[i-1] - A[i-1]) * 2
        if MN[i] <= 0:
            return -1

    if A[N-1] > MN[N-1]:
        return -1

    results = [0 for _ in range(N)]
    results[N-1] = A[N-1]
    if results[N-1] <= 0:
        return -1
    for i in range(N-2, -1, -1):
        results[i] += min(results[i+1] + A[i], MN[i])
        if results[i] <= 0:
            return -1

    return sum(results)

    
    


if __name__ == "__main__":
    print(solve())

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


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

maxs = [1]

for i in range(1,n+1):
    nex = maxs[i-1]*2 - a[i]
    maxs.append(nex)

if(maxs[n] < 0):
    print('-1')
    sys.exit()

results = [a[n]]

for i in range(n):
    if(results[i] > maxs[n-i-1]):
        results.append(maxs[n-i-1]+a[n-i-1])
    else:
        results.append(results[i]+a[n-i-1])


print(sum(results))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
lis = [0] * (n+1)
lis[-1] = a[-1]
for i in range(2, n+2):
    lis[-i] = lis[-i + 1] + a[-i]
now = 1
ans = 0
for i in range(n+1):
    if a[i] > now:
        print(-1)
        exit()
    node = min(now, lis[i])
    ans += node
    node -= a[i]
    now = 2 * node
print(ans)

Solution (Python):
depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []
limited_a = []

def solve (depth) :
    cur = 1
    i = 0 
    while i <= depth :
        limited_a.append( cur )
        if cur <= 0 and leaves[i] != 0 :
            return False
        cur=(cur-leaves[i])*2
        i+=1 
    
    _min = _max = 0
    i = depth
    while i >= 0 :
        if i==depth: 
            if leaves[i] > limited_a[i] :
                return False
            limited.append(leaves[i])
            _max = leaves[i]
            _min = (leaves[i]+1)//2
        else :
            _max = min(limited_a[i], _max+leaves[i])
            _min = (_min+leaves[i]+1)//2
            if _max < _min :
                return False 
            limited.append(_max)
        i -= 1
    return True

if solve(depth) :
    print(sum(limited))
else :
    print (-1)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
if A[0] == 1 and N == 0:
    print(1)
    exit()
if A[0] != 0:
    print(-1)
    exit()
A.reverse()
B = []
ans = 0
num = 0
num2 = 0
for i in range(N+1):
    lim = 2**(N-i)
    if A[i] > lim:
        print(-1)
        exit()
    num = min(num+A[i],lim)
    B.append(num)
A.reverse()
B.reverse()
for i in range(N):
    num2 = B[i]-A[i]
    if num2*2 < A[i+1]:
        print(-1)
        exit()
    if num2*2 < B[i+1]:
        B[i+1] = num2*2
print(sum(B))

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

v = [[0,a] for a in A]
v[0][0] = 1
MAX = 2
for i in range(1,N+1):
    v[i][0] = min((v[i-1][0]-v[i-1][1])*2,leaf)
    leaf -= v[i][1]
    MAX *= 2
v

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

ans = 0

for a,b in v:
    if a <= 0:
        print('-1')
        exit()
    ans += a

print(ans)

Solution (Python):
N = int(input())
A = list( map(int, input().split()) )
B = [i for i in A]

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

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

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

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

if(2*(a-A[-2]) < A[-1]):
  print(-1)
  exit()
print(sum + A[-1])

Solution (Python):








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


sum_a = sum(A)
count = 1
root_num = 1
count_leaf = 0

def calc_node_num(leaf_num, root_num, count_leaf, count):
    count_leaf += leaf_num
    next_root_num = min(root_num*2-leaf_num, sum_a-count_leaf)
    count += (next_root_num + leaf_num)
    return next_root_num, count_leaf, count
    

if (N==0)&(A[0]>0)&(A[0]<=1):
    print(A[0])
elif (N==0)&(A[0]==0):
    print(-1)
elif (N==0)&(A[0]>1):
    print(-1)
else:
    for i in range(1,N+1):
        root_num, count_leaf, count = calc_node_num(A[i], root_num, count_leaf, count)
        if A[0]>0:
            print(-1)
            break
        if (i<N)&(root_num==0):
            print(-1)
            break
        if root_num < 0:
            print(-1)
            break
    else:
        print(count)

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

pa = 1
ch = 1
node = 0
flag = True
A_score = sum(A)

for d in range(N+1):
  pa = ch
  A_score -= A[d]
  if A_score >= (pa - A[d]) * 2:
    ch = (pa - A[d]) * 2
  elif (pa - A[d]) * 2 >= A_score:
    ch = A_score
  else:
    ch = pa - A[d]
  node += pa
  if ch < 0:
    flag = False

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

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


mxs = [1]
for a in A[1:]:
    p = mxs[-1]*2 - a
    if p < 0:
        print(-1)
        exit()
    mxs.append(p)

ans = p = A[-1]
for i in range(N-1,-1,-1):
    if mxs[i]+A[i] < (p+1)//2:
        print(-1)
        exit()
    n = min(p, mxs[i]) + A[i]
    ans += n
    p = n
print(ans)