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):
from math import *


if __name__ == "__main__":
    n = int(input())
    arr = [int(x) for x in input().split(' ')]
    if(arr[0] > 1):
        print("-1")
    else:
        if(n == 0):
            print("1")
        else:
            dp = [0] * (n + 1)
            fl = True
            active_node, dp[0] = 1 - arr[0], 1
            i = 1
            while(fl and i < n):
                max_node = active_node * 2
                if(arr[i] > max_node):
                    fl = False
                else:
                    dp[i] = max_node
                    active_node = max_node - arr[i]
                i = i + 1
            if(fl):
                ans = 0
                max_node = active_node * 2
                if(arr[n] > max_node):
                    print("-1")
                else:
                    dp[-1] = max_node
                    min_req, max_req = 0, 0
                    i = n
                    while(fl and i >= 0):
                        min_req, max_req = min_req + arr[i], max_req + arr[i]
                        if(dp[i] < min_req):
                            fl = False
                        else:
                            curr_node = min(dp[i], max_req)
                            min_req, max_req = curr_node // 2, curr_node
                            ans = ans + curr_node
                        i = i - 1
                    print(ans if(fl) else "-1")
            else:
                print("-1")

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

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

INF = 1e18
B = [1]*(N+1)
for i,a in enumerate(A[1:],1):
    B[i] = min(INF,B[i-1]*2 - a)

ans = 0
p = 0
for i,a in enumerate(A[::-1]):
    i = N - i
    m = B[i]
    if p>2*m:
        ans = -1
        break
    p = min(m,p)+a
    ans += p

print(ans)

Solution (Python):
n = int(input())
a = [int(num) for num in input().split()]
b = [0] * (n+1)
b[n] = a[-1]
for i in range(n):
    b[n-1-i] = b[n-i] + a[-i-2]






ans = 1
fl = True
if a[0] == 0:
    n_dep = 1
elif a[0] == 1 and n == 0:
    fl = False
else:
    ans = -1
    fl = False

if fl:
    for i in range(1,n+1):
        
        if a[i] > n_dep*2:
            ans = -1
            break
        elif n_dep * 2 <= b[i]:
            n_dep *= 2
            ans += n_dep
            n_dep -= a[i]
        else:
            n_dep = b[i] - a[i]
            ans += b[i]
    
print(ans)

Solution (Python):
import sys

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

s=0
for i in A:
    s+=i

S=[]
for i in range(n+1):
    S.append(s)
    s-=A[i]


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

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


ans=1
temp=1
for i in range(n-1):
    
    if A[i+1]>=2*temp:
        print(-1)
        sys.exit()
    else:
        temp=min(S[i+1],2*temp)
        ans+=temp
        temp-=A[i+1]
        

if temp<=A[n]<=2*temp:
    ans+=A[n]
    print(ans)
else:
    print(-1)

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

cap = [1]*(N+1)

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

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

T = [0]*(N+1)
T[N]=A[N]
for i in range(N-1,-1,-1):
    T[i]=A[i]+min(T[i+1],cap[i])

print(sum(T))

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

flag = 0
node_sum = 0
now_node = 0
max_node = [1]
for i in range(1, n+1):
    max_node.append((max_node[i-1]-a_list[i-1])*2)


for d, a in enumerate(reversed(a_list)):
    d = n-d
    max_now = max_node[d]
    if (now_node+1)//2 + a > max_now:
        flag = 1
        break
    elif now_node + a > max_now:
        now_node = max_now
    else:
        now_node += a
    node_sum += now_node
    

if flag == 1:
    print(-1)
else:
    print(node_sum)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()

sumnode = 0
sumleaf = sum(a)

nn = 1
sumnode = 1
if n == 0:
    if a[0] != 1:
        print(-1)
    else:
        print(1)
elif a[0] == 1:
    print(-1)
else:
    for i in range(1,n+1):
        if n == 0:
            print(-1)
            break

        if sumleaf > nn:
            nn = min(nn*2, sumleaf)
        
        sumnode += nn

        nn -= a[i]
        if nn < 0:
            print(-1)
            break
        sumleaf -= a[i]

        
    else:
        print(sumnode)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

minN, maxN = A[N], A[N]

mins = [0] * (N + 1)
maxs = [0] * (N + 1)


mins[N], maxs[N] = A[N], A[N]
for i in range(N - 1, -1, -1):
    mins[i] = (mins[i + 1] + 1) // 2 + A[i]
    maxs[i] = maxs[i + 1] + A[i]




def ok():
    c = 1
    ret = 0
    for i in range(N + 1):
        if not mins[i] <= c:
            return -1
        c = min(c, maxs[i])
        ret += c
        
        c = 2 * (c - A[i])

    return ret

print(ok())

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    A_sum = sum(A)
    ans = 1
    tmp_v = 1
    if A[0] > 1:
        print(-1)
        sys.exit()
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
        sys.exit()
    for i in range(N):
        if A[i+1] > tmp_v*2:
            print("-1")
            sys.exit()
        tmp_v = min(tmp_v*2, A_sum)
        ans += tmp_v
        A_sum -= A[i+1]
        tmp_v -= A[i+1]
    print(ans)



if __name__ == '__main__':
    main()

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

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

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


corr_flag = 1
if A[-1] > capacity[-1]:
    corr_flag = 0
curr = A[-1]
ans = A[-1]
for i in range(N-1, -1, -1):
    curr = min(capacity[i], A[i] + curr)
    ans += curr
if corr_flag:
    print(ans)
else:
    print(-1)

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

backward = [0]
for a in reversed(A):
    backward.append(backward[-1] + a)
backward.reverse()
backward.pop()

backward_lower = [0]
for a in reversed(A):
    backward_lower.append((backward_lower[-1] + 1) // 2 + a)
backward_lower.reverse()
backward_lower.pop()

forward = [1]
for i in range(N):
    forward.append((forward[-1] - A[i]) * 2)
    if forward[-1] > backward[i]:
        break


ans = 0
for i in range(N + 1):
    if i < len(forward):
        if backward_lower[i] > forward[i]:
            print(-1)
            break
        ans += min(forward[i], backward[i])
    else:
        ans += backward[i]
else:
    print(ans)

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

A=[int(i) for i in input().split()]
B=[0 for i in range(n+1)]
C=[0 for i in range(n+1)]
D=[0 for i in range(n+1)]
ck=[0 for i in range(n+1)]


now=A[-1]
B[-1]=now
C[-1]=now
D[-1]=now
for i in range(n):
    q=n-1-i
    if now%2==1:
        ck[q]=1
    C[q]=now//2
    now=now//2+A[q]+now%2
    B[q]=now
    D[q]=D[q+1]+A[q]

ans=sum(B)

bonus=0
BON=[0]
for i in range(1,n):
    bonus*=2
    bonus+=ck[i-1]
    bonus=min(bonus,D[i]-B[i])
    BON.append(bonus)
    ans+=bonus

if B[0] != 1:
    print(-1)
else:
    print(ans)

Solution (Python):
n = int(input())
ns = list(map(int, input().split()))
li = 1
ans = 0
max_leafs = [1]
for i in ns:
    li = (li - i) * 2
    max_leafs.append(li)
points = ns.pop()
ans += points
for i in range(len(ns)-1, -1, -1):
    a = ns[i]
    points = min(points + a, max_leafs[i])
    ans += points
if max_leafs[-1] < 0:
    print(-1)
else:
    print(ans)

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

mid_node = [(0,0) for i in range(N+1)]
for i in range(N-1, -1, -1):
	m,M = mid_node[i+1]
	child_leaf = A[i+1]
	mid_node[i] = ((child_leaf + m + 1)//2, child_leaf + M)

def between(n,a,b):
	return a <= n and n <= b
ans = [0 for i in range(N+1)]
if not between(1, mid_node[0][0], mid_node[0][1]):
	print(-1)
	exit()

ans[0] = (1, 0)
for i in range(1, N+1):
	b_m = ans[i-1][0]
	node_min, node_max = mid_node[i][0] + A[i], mid_node[i][1] + A[i]
	candidate_min, candidate_max = b_m, b_m*2
	if candidate_min > node_max or candidate_max < node_min:
		print(-1)
		exit()
	node = min(candidate_max, node_max)
	ans[i] = (node - A[i], A[i])
print(sum([a+b for a,b in ans]))

Solution (Python):
from math import log2
n = int(input())
arr = list(map(int, input().split()))

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

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

arr.reverse()

ar2 = [None] * (n+1)

for i, e in enumerate(arr):
    if i == 0:
        ar2[0] = (e, e)
        continue

    ar2[i] = (ar2[i-1][0]+e, (ar2[i-1][1]+1) // 2 + e)

if ar2[-1][1] > 1:
    print(-1)
    exit()

ar2.reverse()

total = 0
acc = 1
for i, t in enumerate(ar2):
    acc = min(acc, t[0])

    total += acc
    acc -= arr[n-i]
    acc *= 2

print(total)

Solution (Python):
def main():

    N = int(input())
    A = list(map(int, input().split()))
    SA = [0]
    for i in range(N + 1):
        SA.append(SA[-1] + A[N - i])
    SA.reverse()
    res = 0
    t = 1
    for i in range(N + 1):
        if t >= SA[i]:
            t = SA[i]
        res += t
        t -= A[i]
        if t <= 0:
            if i != N:
                return -1
            else:
                if t < 0:
                    return -1
        t *= 2
    return res


print(main())

Solution (Python):
def Csum(a):
    b,c=[0],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=Csum(a)
su=sum(a)
b=1
c=0
for i in range(n+1):
    c+=b
    b-=a[i]
    if b<=0:
        if i==n and b==0:
            break
        print(-1)
        exit()
    b=min(b*2,su-s[i+1])
print(c)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")











N = int(input())
A = list(map(int,input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
elif A[0] != 0:
    print(-1)
else:
    band1 = deque([[A[N],A[N]]])
    for i in range(N):
        x = A[N-1-i]
        MIN = band1[0][0]
        MAX = band1[0][1]
        vmin = x+(MIN+1)//2
        vmax = MAX + x
        band1.appendleft([vmin,vmax])
    band1 = list(band1)
    band2 = [[1,1]]
    for i in range(1,N+1):
        p = A[i-1]
        MIN = band2[i-1][0] - p
        MAX = band2[i-1][1] - p
        vmin = MIN
        vmax = 2*MAX
        band2.append([vmin,vmax])
    c = 0
    ans = 0
    for i in range(N+1):
        li1 = band1[i]
        li2 = band2[i]
        if li1[1] < li2[0] or li1[0] > li2[1]:
            c = 1
            break
        else:
            ans += min(li1[1],li2[1])
    if c == 0:
        print(ans)
    else:
        print(-1)

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

G = []
nodes = [0]*(N+1)
nodes[0] = 1
for i in range(N):
    nodes[i+1] = nodes[i]*2

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

ans = 0
node = 1 - A[0]
nodes = [0 for i in range(N)]
nodes[0] = 1 - A[0]  


for i in range(1, N+1):
    if i == N:
        if math.ceil(A[i]/2) > nodes[i-1]:
            print(-1)
            exit(0)
        else:
            continue
    else:
        
        if nodes[i-1] * 2 >= A[i]:
            nodes[i] = nodes[i-1] * 2 - A[i]
        else:
            print(-1)
            exit(0)
ans += A[i]
prev = A[-1]
for i in range(N-1, -1, -1):
    
    prev = min(nodes[i], prev) + A[i]
    ans += prev

print(ans)

Solution (Python):
from itertools import accumulate
N,*A=map(int, open(0).read().split())
if N==0:
    if A[0]==1:
        print(1)
    else:
        print(-1)
    exit()
if A[0]!=0:
    print(-1)
    exit()
R=[0]*(N+2)
R[0]=1
ans=0
for i in range(N+1):
    R[i]-=A[i]
    if R[i]<0:
        print(-1)
        exit()
    R[i+1]=min(R[i]*2,10**17)
B=list(accumulate(A[::-1]))[::-1]
ans+=sum(min(R[i]+A[i],B[i])for i in range(N+1))
print(ans)

Solution (Python):
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def Yes(x):print("Yes")if x==True else print("No")
n=N()
l=L()
if n==0:
    if l[0]==1:
        print(1)
    else:
        print(-1)
    quit()
if l[0]==1:
    if sum(l)==1:
        print(1)
    else:
        print(-1)
    quit()
ans=[0]*(n+1)
v=1
ans[0]=1
for i in range(1,n+1):
    v*=2
    ans[i]=v
    v-=l[i]
    if v<0:
        print(-1)
        quit()
for i in range(n,0,-1):
    ans[i]-=v
    if ans[i]>=ans[i-1]-l[i-1]:
        break
    v=ans[i-1]-l[i-1]-ans[i]
print(sum(ans))

Solution (Python):
import math

N = int(input())

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

List_re = list(reversed(List))
arr = [-1 for i in range(N+1)]
arr2 = [-1 for i in range(N+1)]
arr3 = [-1 for i in range(N+1)]

for i in range(N+1):
  a = List_re[i]
  if i == 0:
    arr3[N-i] = a    
  else:
    arr3[N-i] = math.ceil(arr3[N-i+1]/2) + a

for i in range(N+1):
  a = List_re[i]
  if i == 0:
    arr[N-i] = a    
  else:
    arr[N-i] = arr[N-i+1] + a
    
for i in range(N+1):
  a = List[i]
  if i == 0:
    arr2[i] = 1
  else:
    arr2[i] = ( arr2[i-1]-List[i-1]) *2

ans = 0

for i in range(N+1):
  a = arr[-i-1]
  b = arr2[-i-1]
  c = min(a,b)
  ans += c

if arr3[0] != 1:
  print(-1)
else:
  print(int(ans))

Solution (Python):
def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

def cum_sum(lst):
    cums = [0] * (len(lst)+1)
    cums[1] = lst[0]
    for i in range(2,len(lst)+1):
        cums[i] = cums[i-1] + lst[i-1]
    return cums


n = int(input())
a = lmp()
ar = list(reversed(a))
amx = [1]
for i in range(n):
    u = (amx[i]-a[i])*2
    if u <= 0:
        print(-1)
        exit()
    else:
        amx.append(u)
arcum = cum_sum(ar)[1:]
arcum = list(reversed(arcum))


if amx[-1] < arcum[-1]:
    print(-1)
    exit()
cnt = 0
for i in range(n+1):
    cnt += min(amx[i],arcum[i])
print(cnt)

Solution (Python):
import sys
from itertools import accumulate as accum

input = sys.stdin.readline


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

    B = list(accum((A[1:])[::-1]))[::-1]

    ans = 1
    v_count = 1
    for a, b in zip(A[:-1], B):
        if a > 0:
            if a > v_count:
                ans = -1
                break
            else:
                v_count -= a
        v_count = min(2 * v_count, b)
        ans += v_count

    if v_count != A[-1]:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = [0 for i in range(N+1)]
S = sum(A)
B[0]=1
flag=1
if A[0]>1 :
    flag=0
if A[0]>0 and N>0:
    flag=0

for i in range(N):
    if flag==0:
        break

    S = S-A[i]

    if 2*(B[i]-A[i])<A[i+1]:
        flag = 0

    B[i+1]=min(2*(B[i]-A[i]),S)

if flag==0:
    print(-1)
else:
    res = sum(B)
    print(res)

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

def check():
    R = [0]*(N+1)
    R[0] = 1
    for i in range(N):
        if R[i] < A[i]:
            return -1
        R[i+1] = 2*(R[i]-A[i])
    if R[N] < A[N]:
        return -1
    
    
    CA = A[:]
    
    for i in range(N-1, -1, -1):
        CA[i] += CA[i+1]
    
    
    return sum(min(r, c) for r, c in zip(R, CA))


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

if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
elif A[0] or A[N] == 0:
    print(-1)
else:
    print(check())

Solution (Python):
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e25)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

num = sum(a)
ans = 0
ko = 1
for i in range(N):
  ans += ko
  ko -= a[i]
  num -= a[i]
  ko = min(ko*2, num)

  if ko <= 0:
    print(-1)
    break
else:
  ans += ko
  ko -= a[-1]
  if ko < 0:
    print(-1)
  else:
    print(ans)

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

n = [0]*(N+1)
n[0] = 1
for d in range(1,N+1):
    n[d] = min(Ac[N]-Ac[d-1],2*(n[d-1]-A[d-1]))
if n[N]!=A[N]:
    ans = -1
else:
    ans = sum(n)
print(ans)

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

RG1 = [None]*N
d = u = 1
for i in range(N):
    d = max(0, d - A[i+1])
    u = max(0, 2*u - A[i+1])
    RG1[i] = (d,u)

RG2 = [None]*N
d = u = 0
for i in range(N-1,-1,-1):
    RG2[i] = (d,u)
    d = (d+A[i+1]+1)//2
    u = u + A[i+1]

RG3 = [ (max(RG1[i][0],RG2[i][0]), min(RG1[i][1],RG2[i][1])) 
        for i in range(N)]

ans = 1 + sum(A)
for i in range(N):
    if RG3[i][0] > RG3[i][1]:
        print(-1)
        exit()
    else:
        ans += RG3[i][1]
print(ans)

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

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

def check():
	b_max = 0
	b_min = 0
	b_max_list = [0]
	for a in reversed(A_list):

		b_max = a + b_max
		b_max_list.append(b_max)
		b_min = (a + b_min + 1) // 2
	
	b_max_list.pop()
	
	count = 0
	branches = 1
	for a, b_max in zip(A_list, reversed(b_max_list)):
		if branches < a:
			return -1

		if branches <= 0:
			return -1

		count += branches
		branches = min(b_max, (branches - a) * 2)
	
	return count

result = check()
if result != None:
	print(result)
else:
	print(-1)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    import sys
    class Lazysegtree():
        """RAQ
        外から使うのは，query，add,updateくらいか
        
        """
        def __init__(self, A, intv, initialize = True, segf = min):
            """
            Aが初期配列，intvが単位元,segfが評価関数
            """
            
            
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.intv = intv
            self.segf = segf
            self.lazy = [0]*(2*self.N0)
            if initialize:
                self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [intv]*(2*self.N0)

        def _ascend(self, k):
            k = k >> 1
            c = k.bit_length()
            for j in range(c):
                idx = k >> j
                self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) \
                + self.lazy[idx]
                
        def _descend(self, k):
            k = k >> 1
            idx = 1
            c = k.bit_length()
            for j in range(1, c+1):
                idx = k >> (c - j)
                ax = self.lazy[idx]
                if not ax:
                    continue
                self.lazy[idx] = 0
                self.data[2*idx] += ax
                self.data[2*idx+1] += ax
                self.lazy[2*idx] += ax
                self.lazy[2*idx+1] += ax
        
        def update(self, k, x):
            
            k = k + self.N0
            self.data[k] = x
            self._ascend(k)
        
        def query(self, l, r):
            
            L = l+self.N0
            R = r+self.N0
            Li = L//(L & -L)
            Ri = R//(R & -R)
            self._descend(Li)
            self._descend(Ri - 1)
            
            s = self.intv                                                              
            while L < R:
                if R & 1:
                    R -= 1
                    s = self.segf(s, self.data[R])
                if L & 1:
                    s = self.segf(s, self.data[L])
                    L += 1
                L >>= 1
                R >>= 1
            return s
        
        def add(self, l, r, x):
            
            L = l+self.N0
            R = r+self.N0

            Li = L//(L & -L)
            Ri = R//(R & -R)
            
            while L < R :
                if R & 1:
                    R -= 1
                    self.data[R] += x
                    self.lazy[R] += x
                if L & 1:
                    self.data[L] += x
                    self.lazy[L] += x
                    L += 1
                L >>= 1
                R >>= 1
            
            self._ascend(Li)
            self._ascend(Ri-1)

            
    
    
    mod=10**9+7
    N=I()
    A=LI()
    A[-1]-=1
    if A[0]!=0:
        ans=-1
            
    else:
        ans=N+1
        now=0
        seg=Lazysegtree([1]*(N+1), 10**10, True, min)
        for i in range(1,N+1):
            a=A[i]
            if ans==-1:
                break
            while a>0:
                if now==i:
                    ans=-1
                    break
                
                cap=seg.query(now,now+1)
                
                if a>=cap:
                    a-=cap
                    
                    seg.add(now+1,i,cap)
                    ans+=(i-now)*cap
                    now+=1
                    
                else:
                    
                    
                    seg.add(now,now+1,-a)
                    seg.add(now+1,i,a)
                    ans+=(i-now)*a
                    a=0
                    


                
            
            
    print(ans)
        

main()

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

n = 1
result = 0
S = sum(A)

for i in range(N+1):
    result += n

    if n < A[i]:
        print(-1)
        break
    n -= A[i]
    S -= A[i]

    if n < S:
        if n*2 < S:
            n *= 2
        else:
            n = S
else:
    print(result)

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline



def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n = gete(int)
    a = tuple(geta(int))
    s = sum(a)

    cur = 1
    ans = 0

    for ai in a:
        if cur < ai:
            print(-1)
            exit()
        else:
            ans += min(cur, s)
            cur = 2 * (min(cur, s) - ai)
            s -= ai

    print(ans)


if __name__ == "__main__":
    main()

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

is_possible = True
for i in range(n):
    if a[i] > 2**i - 1:
        is_possible = False
        break
if a[n] > 2**n:
    is_possible = False

s = 0
for i in range(n + 1):
    s += a[i] * (2**(n - i))
if s > 2**n:
    is_possible = False

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

c = [0] * (n + 1)
c[n] = a[n]
ans = a[n]
for i in reversed(range(n)):
    if (c[i + 1] + 1) // 2 + a[i] + b[i] > 2**i:
        is_possible = False
        break
    c[i] = min(c[i + 1], 2**i - a[i] - b[i]) + a[i]
    ans += c[i]





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

Solution (Python):
n=int(input())
a = list(map(int,input().split()))
i=0
b=0
while i<=n:
    b+=a[i]
    i+=1
i=0
x=1
ans=0
while i<=n:
    if a[i] <=x:
        if x<=b:
            ans+=x
            x=(x-a[i])*2
        else:
            ans+=b
            x = b
        b-=a[i]
    else:
        ans=-1
        break
    i+=1
print(ans)

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

    if leaf<0 or (leaf==0 and m>0):
        print(-1)
        sys.exit()

    tmp=leaf
    for j in range(min(n-i,60)):
        tmp*=2
        if tmp>=m: break
    if tmp<m:
        print(-1)
        sys.exit()        

    if leaf*2>=m: leaf=m
    else: leaf*=2

print(ans)

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

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

Solution (Python):
def main():
  n=int(input())
  anums=list(map(int,input().split()))
  mx_nonleaves=[0 for _ in range(n+1)]
  if n==0:
    if anums[0]==1:
      return 1
    return -1
  for i,anum in enumerate(anums):
    if i==0:
      if anum>0:
        return -1
      mx_nonleaves[i]=1
      continue
    mx_nonleaves[i]=mx_nonleaves[i-1]*2-anums[i]
    if mx_nonleaves[i]<0:
      return -1
  mx_nonleaves[-1]=0
  
  for idx in range(n,1,-1):
    mx_nonleaves[idx-1]=min(mx_nonleaves[idx-1],mx_nonleaves[idx]+anums[idx])
  
  
  return sum(anums)+sum(mx_nonleaves)

print(main())

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()

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

tw[0] = 1
no = 1
for i in range(1,n+1):
	tw[i] = no*2
	no = no*2 - a[i]


ans = 0

if n == 0:
	if a[0] == 1:
		print(1)
	else:
		print(-1)
else:
	if a[0] != 0:
		print(-1)
		exit()
	ans = 0
	co = 0
	for i in range(n,0,-1):
		if i == n:
			if tw[i] < a[i]:
				print(-1)
				exit()
			else:
				co = a[i]
				ans += a[i]
		else:
			if a[i] + co <= tw[i]:
				ans += a[i] + co
				co = a[i] + co
			else:
				if -(-co//2) + a[i] <= tw[i]:
					ans += tw[i]
					co = tw[i]
				else:
					print(-1)
					exit()

	print(ans+1)

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] != 0:
    print(-1)
    exit()

s = sum(a)
ans = 1
m = 1
flag = True
for i in range(1, n+1):
    if flag:
        m *= 2
        if m > s:
            m = s
            flag = False
    ans += m
    if a[i] > m:
        print(-1)
        exit()
    m -= a[i]
    s -= a[i]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    A = list(map(int,input().split()))
    can_root = [0] * (N + 1)
    can_root[0] = 1
    if N > 0 and A[0] >= 1:
        print(-1)
        return 
    if N == 0 and A[0] == 1:
        print(1)
        return
    if N == 0 and A[0] >= 2:
        print(-1)
        return

    for i in range(1,N + 1):
        can_root[i] = 2*can_root[i - 1] - A[i]
        if i < N:
            if can_root[i] <= 0:
                print(-1)
                return 
        if i == N:
            if can_root[i] < 0:
                print(-1)
                return
    
    ans = A[-1]
    now = A[-1]
    for i in range(N - 1,-1,-1):
        if now <= can_root[i]:
            now += A[i]
        else:
            now = can_root[i] + A[i]
        ans += now
    print(ans)
if __name__ == '__main__':
    main()

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]>0:
  print(-1)
  exit()

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

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

Solution (Python):
import sys
n = int(input())
p = list(map(int, input().split()))
sum_p = sum(p)-1
ans = 1
tmp = 1 - p[0]
if n==0 and p[0]==1:
    print(1)
    sys.exit()
elif n == 0:
    print(-1)
    sys.exit()

for i in range(n):
    if sum_p:
        if sum_p < tmp:
            tmp += sum_p
            sum_p = 0
        else:
            sum_p -= tmp
            tmp *= 2    
    ans += tmp
    tmp -= p[i+1]
    if tmp < 0 or (tmp==0 and i<n-1):
        print(-1)
        sys.exit()
print(ans)