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 A[0]>=2:
  print(-1)
  
elif A[0]==1:
  if N!=0:
    print(-1)
  else:
    print(1)
    
else:
  SA = sum(A)
  ans = 1
  parent = 1
  judge = True
  for i in range(1, N+1):
    num_leaf = A[i-1]
    num_child = 2*(parent - num_leaf)
    SA -= num_leaf
    if (num_child<A[i])or(num_child<1):
      judge = False
      break
      
    if num_child<=SA:
      parent = num_child
      ans += num_child
      
    else:
      parent = SA
      ans += SA

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

Solution (Python):

n=int(input())
A=list(map(int,input().split()))
flag=True
check=True
cnt=sum(A)-1
f=1
ans=1
dis=0
for i in range(n+1):
    if A[i]<=f:
        dis+=A[i]*(n-i)
        if check:
            if cnt==0:
                ans+=n
                check=False
            elif cnt>f-A[i]:
                ans+=(f-A[i])*(n-i)
                cnt=cnt-(f-A[i])
            else:
                ans+=cnt*(n-i)
                cnt=0
        f=2*(f-A[i])
    else :
        flag=False
        break
if not flag:
    print(-1)
else:
    print(ans-dis)

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 0 and A[0] == 1:
        print(1)
        return
    if N == 0:
        print(-1)
        return
    if A[0] != 0:
        print(-1)
        return
    
    
    B = [0] * (N + 1)
    B[-1] = A[-1]
    for i in range(N - 1, -1, -1):
        B[i] = B[i + 1] + A[i]
    
    
    vertex = 1
    root = 1
    for i in range(1, N):
        if root * 2 - 1 < A[i]:
            print(-1)
            return
        if root < A[i]:
            root = min(B[i + 1], root * 2 - A[i])
            vertex += A[i] + root
        else:
            root = min(B[i + 1], root * 2 - A[i])
            vertex += A[i] + root
    
    
    if root * 2 < A[-1]:
        print(-1)
        return
    vertex += A[-1]
    print(vertex)
    





if __name__ == "__main__":
    main()

Solution (Python):
n,*a=map(int,open(0).read().split())
ans=0
store=1
leaves=sum(a)
for i in range(n+1):
  if a[i]>store:
    ans=-1
    break
  node=min(store,leaves)
  ans+=node
  leaves-=a[i]
  store-=a[i]
  store*=2
print(ans)

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

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

sum_ue = [1]
sum_shita = [A[N]]

for i in range(N):
    sum_ue.append((sum_ue[i] - A[i]) * 2)
    sum_shita.append(sum_shita[i] + A[N - 1 - i])

sum_shita.reverse()



ans = 0

for i in range(N + 1):
    if i == N:
        if sum_ue[i] < A[i]:
            print(-1)
            exit()
    else:
        if sum_ue[i] <= A[i]:
            print(-1)
            exit()

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

print(ans)

Solution (Python):
N = int(input())
l = [int(x) for x in input().split()]
ans = 1
wa = sum(l)
kosuu = 1 - l[0]
flag = 0
if N == 0:
    if l[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
for i in range(1,N):
    if  flag == 0:
        kosuu = kosuu * 2
    if kosuu >= wa:
        flag = 1
        kosuu = wa
    ans += kosuu
    kosuu = kosuu - l[i]
    wa = wa-l[i]
    if kosuu <= 0:
        print(-1)
        exit()
if kosuu*2 < l[N]:
    print(-1)
else:
    print(ans+l[N])

Solution (Python):

from itertools import accumulate

def main():
    N = int(input())
    A = list(map(int, input().split()))
    accumA = list(accumulate(A[::-1]))[::-1]
    ans = 1
    ne = [0] * (N+1)
    ne[0] = 1

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


    for i in range(1,N+1):
        if i == N:
            if ne[i-1] > A[i] or ne[i-1] * 2 < A[i]:
                print(-1)
                exit()
            else:
                ans += A[i]
        else:
            tmp_ne = min(ne[i-1]*2 - A[i], accumA[i+1])
            if tmp_ne < 0:
                print(-1)
                exit()
            else:
                ne[i] = tmp_ne
                ans += tmp_ne + A[i]
    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)
else:
    req = [0] * n
    req[-1] = a[-1]
    for i in range(2, n+1):
        req[-i] = req[-(i-1)] + a[-i]
    l = [0] * (n + 1)
    l[0] = 1
    for i in range(1, n+1):
        M = (l[i-1] - a[i-1]) * 2
        l[i] = min(M, req[i-1])
    if l[-1] < a[-1]:
        print(-1)
    else:
        print(sum(l))

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
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    def min2(x, y): return x if x <= y else y

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

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

    pow2 = 1
    pow2s = [pow2]
    for d in range(61):
        pow2 *= 2
        pow2s.append(pow2)
    pow2s += [pow2] * N


    maxV = min2(1, 1-As[0])
    maxVs = [maxV]
    for d in range(1, N+1):
        maxV = min2(maxV*2, pow2s[d]) - As[d]
        maxVs.append(maxV)


    numVs = [0] * (N+1)
    numVs[N] = As[N]
    for d in reversed(range(N)):

        numC2 = -(-numVs[d+1] // 2)

        if maxVs[d] < numC2:
            return -1
        num = min2(maxVs[d], numVs[d+1])
        numVs[d] = As[d] + num

        if numVs[d] > pow2s[d]:
            return -1


    return sum(numVs)


ans = solve()
print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  

N = I()
A = LI()
a = sum(A)

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[0] = 1

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

ans = A[N]

r = A[N]
for i in range(N-1,-1,-1):
    ans += A[i] + min(B[i],r)
    r = A[i]+min(B[i],r)

print(ans)

Solution (Python):
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7




class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
N += 1

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



























bit = BinaryIndexedTree(size=N + 10)
bit.add(0, 1)
bit.add(N - 1, -1)
A[-1] -= 1

d = 0
ok = True
ans = N
for i in range(N):
    while A[i] > 0:
        
        if d >= i:
            ok = False
            break
        
        a = min(A[i], bit.sum(d + 1))
        A[i] -= a

        
        bit.add(d, -a)
        bit.add(d + 1, a)
        
        bit.add(d + 1, a)
        bit.add(i, -a)

        
        ans += a * (i - d)
        while d < N and bit.sum(d + 1) <= 0:
            d += 1

    if not ok:
        break
    
    
    
    
    
if ok:
    print(ans)
else:
    print(-1)
exit()

Solution (Python):
n=int(input())
a=[int(j)for j in input().split()]
ans=0
s=sum(a)
p=1
b=True
for i,j in enumerate(a):
    if p<j:
        print(-1)
        exit()
    ans+=p
    p-=j
    s-=j
    if i==n:
        continue
    if p<s and b:
        if p*2<s:
            p*=2
        else:
            p=s
    if p==s:
        b=False
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a2 = [0] * (n + 1)
d = [1] * (n + 1)
ans = 1
a2[0] = sum(a)
for i in range(n):
    a2[i + 1] = a2[i] - a[i + 1]
for i in range(n):
    if d[i] - a[i] <= 0:
        ans = -1000000000000
    if (d[i] - a[i]) * 2 >= a2[i]:
        d[i + 1] = a2[i]
    else:
        d[i + 1] = (d[i] - a[i]) * 2

if ans < 0:
    ans = -1
elif d[n] != a[n]:
    ans = -1
else:
    ans = sum(d)
print(ans)

Solution (Python):
n=int(input())
a=[int(j)for j in input().split()]
ans=0
s=sum(a)
p=1
b=True
for i,j in enumerate(a):
    if p<j:
        print(-1)
        exit()
    ans+=p
    p-=j
    s-=j
    if i==n:
        continue
    if p<s and b:
        if p*2<s:
            p*=2
        else:
            p=s
    if p==s:
        b=False

print(ans)

Solution (Python):
n = int(input())
v = list(map(int, input().split()))
u = [1]*(n+1)
a = 0
b = False
tmp = 0
tt = 0
for i in range(n+1):
  if u[i] < v[i]:
    b = True
    break
  if i < n:
    u[i+1] = (u[i] - v[i])*2
for i in range(n, -1, -1):
  tt += v[i]
  tmp = min(tt, u[i])
  a += tmp
  tt = tmp
if n == 0:
  a = v[0]
if b:
  a = -1
print(a)

Solution (Python):
def main(N, A):
    num = 1
    ans = 1
    for i in range(N+1):
        num -= A[i]
        if i < N:
            num *= 2
            ans += num
        if num == 0 and i < N:
            return -1
        if num < 0:
            return -1
    eda = 0
    for i in range(N+1):
        ans -= num
        eda += A[N-i]
        num -= eda
        num = num//2
        if num <= 0:
            break
    return ans


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

print(main(N, A))

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]
    Low = [low]
    for b in B[1:]:
        low = max(1, (low+1)//2) + b
        high = high + b
        Hight.append(high)
        Low.append(low)
    if low > 1:
        print(-1)
        return
    ans = 1
    now = 1
    BHight = Hight[::-1]
    BLow = Low[::-1]
    for i in range(1,N+1):
        high = BHight[i]
        low = BLow[i]
        if high < now or now*2 < low:
            print(-1)
            return
        leaf = A[i]
        now = min(high, now*2)
        ans += now
        now -= leaf
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())+1
ali = list(map(int,input().split()))
nli = [0]*N

maxn = 2**(N-1)
nli[-1] = ali[-1]

for i in range(1,N+1):
  nli[-i] = min(maxn,nli[-i+1] + ali[-i])
  maxn //= 2
  

ulim = 1
for i in range(N):
  nli[i] = min(nli[i],ulim)
  ulim = (ulim - ali[i])*2
  if ulim < 0:
    print(-1)
    exit()
  
print(sum(nli))

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    if n == 0 and a[0] == 0:
        print(-1)
        exit()
    elif n == 0 and a[0] == 1:
        print(1)
        exit()
    elif n == 0 and a[0] > 1:
        print(-1)
        exit()
    suma = sum(a)
    ans = a[0]
    can = 1
    for i,ai in enumerate(a):
        if ai > can:
            print(-1)
            exit()
        suma -= ai
        ans += can
        if (can-ai)*2 >= suma:
            can = suma
        else:
            can = (can-ai)*2

    print(ans)




    return

if __name__ == '__main__':
    main()

Solution (Python):

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

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

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

for i in range(n):
    here = a[1+i]
    possible = num[i][0]*2
    num[i+1] = [possible-here,here]
    


if(num[-1][0]<=-1):
    print(-1)
    exit()

num[-1][0] = 0

for i in range(n-1,-1,-1):
    if(num[i+1][0]+num[i+1][1]<num[i][0]):
        num[i][0] = num[i+1][0]+num[i+1][1]



if(num[n][0]>=1):
    print(-1)
    exit()

for i in range(n):
    if(num[i][0]<=0):
        print(-1)
        exit()

s = sum([sum(num[i]) for i in range(n+1)])
print(s)

Solution (Python):
from collections import deque
import sys


def input():
    return sys.stdin.readline().rstrip()


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

ans, nd = 0, 0
lim = [1 for _ in range(N + 2)]
for i in range(N):
    lim[i+1] = (lim[i] - v[i]) * 2

for i in range(N, -1, -1):
    if v[i] + nd > lim[i] * 2 or lim[i] - v[i] < 0:
        print(-1)
        sys.exit(0)
    if v[i] + nd > lim[i]:
        nd = lim[i] - v[i]

    nd += v[i]
    ans += nd

print(ans)

Solution (Python):
import sys
N = int(input())
A = list(map(int,input().split()))
B = []
tmp = 1
for i in range(N+1):
    B.append(tmp)
    tmp -= A[i]
    if tmp < 0:
        print(-1)
        sys.exit()
    tmp *= 2

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

ans = 0

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

print(ans)

Solution (Python):

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

s=0
cap=[]
flag=False
ans=2**(n+1)-1
for i,a in enumerate(A):
    s*=2
    s+=a
    cap.append(2**i-s)
    
    
    if s>2**i:
        flag=True
        break

if flag:
    print(-1)
else:
    remain=2**n-s
    ans=0
    node=0
    for i in range(n,-1,-1):
        a=A[i]
        c=cap[i]
        node=min(c,node)+a
        ans+=node
    print(ans)

Solution (Python):
import sys
msg = sys.stdin.readlines()
n = int(msg[0])
a = list(map(int,msg[1].split()))
tot = 0
b = [0 for i in range(n+1)]
for i in range(n+1):
  b[i] = (1<<i)-2*tot;
  tot = 2*tot+a[i];
  if tot > (1<<i):
    print(-1)
    exit(0)
nb = 0
crt = 0;
for i in range(n,-1,-1):
  crt = min(crt+a[i],b[i])
  nb += crt;
print(nb)

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

if N==0:
    A0 = A[0]
    if A0 == 1:
        print(1)
    else:
        print(-1)
else:
    max_forward = [1]
    now = 1
    flag = 0
    for i in range(N):
        now = (now - A[i])*2
        if now <= 0:
            flag = -1
            break
        max_forward.append(now)
    
    max_backward = [A[-1]]
    now = A[-1]
    for i in range(N):
        ind = N-i-1
        now = now + A[ind]
        max_backward.append(now)
    
    if flag == -1:
        print(-1)
    else:
        if max_forward[-1] < A[-1]:
            print(-1)
        else:
            ans = 0
            for i in range(N+1):
                temp = min(max_forward[i], max_backward[N-i])
                
                ans += temp
            print(ans)

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

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))
n=n_in()
A=l_in()

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[0] = 1

upper = max(A)

S=[0]*(n+1)
S[0] = A[0]

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



for i in range(1, n):
    B[i] = min(B[i-1]*2-A[i], S[n]-S[i])
    if B[i] <= 0:
        print(-1)
        exit()

if A[n] > B[n-1]*2:
    print(-1)
    exit()
        
print(sum(A)+sum(B))

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = 10**9


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

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

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

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


if __name__ == '__main__':
    main()

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


imsi=0   
for i in range(n+1):
    imsi+=l[i]*power[n-i]


if(imsi<=power[n]):
    sum=0
    for i in range(n+1):
        sum+=l[i]
    yuksum=[sum]
    for i in range(n+1):
        yuksum.append(yuksum[-1]-l[i])

    x=1
    parent=1
    for i in range(n+1):
        if i==0:
            pass
        else:
            if (2*parent-l[i])>yuksum[i+1]:
                x+=yuksum[i+1]+l[i]
                parent=yuksum[i+1]
            else:
                x+=2*parent
                parent=2*parent-l[i]
    print(x)
else:
    print("-1")

Solution (Python):
n,*a = map(int,open(0).read().split())
pm = sum(a)
e = 1
te = 1
for i in a:
  pm -= i
  e = min((e-i)*2,pm)
  te += e
  if e < 0:
    break
if e < 0:
  print(-1)
else:
  print(te)

Solution (Python):

N = int(input())
A = [int(k) for k in input().split()]


M = [1]
for a in A[:-1]:
    M.append((M[-1] - a) * 2)


dsum = 0
d = 0
ok = True
for i in range(len(A) - 1, -1, -1):
    min_d = ((d + 1) // 2 if d % 2 else d // 2) + A[i]
    max_d = d + A[i]
    if min_d > M[i]:
        ok = False
        break
    d = min(M[i], max_d)
    dsum += d

print(dsum if ok else -1)

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

flag=True
dp = [[0,0] for _ in range(n+1)]
if a[0]==0:
    dp[0]=[0,1]
    if n==0:
        flag=False
elif a[0]==1:
    dp[0]=[1,0]
else:
    flag=False
for i in range(1,n+1):
    free = dp[i-1][1]*2
    occu = a[i]
    if free-occu<0:
        flag=False
        break
    else:
        free-=occu
    dp[i]=[occu,free]
dp[n][1]=0
ans=0
ch=1001001001
for i in reversed(range(n+1)):
    free=min(ch,dp[i][1])
    ch=dp[i][0]+free
    ans+=dp[i][0]+free

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

Solution (Python):
import os
from collections import defaultdict

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

pow2 = defaultdict(int)

ret = 0
lim = [0] * (N + 1)



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

for d in reversed(range(N + 1)):
    
    
    
    if d == N:
        
        n = A[d]
    else:
        
        n = A[d] + min(n, lim[d])
    ret += n

print(ret)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
A = IL()

if len(A) == 1:
  if A == [1]:
    print(1)
    exit()
  else:
    print(-1)
    exit()
ans = [1]

for a in A[1:]:
  pmax = ans[-1]
  if a > pmax*2:
    print(-1)
    exit()
  else:
    pmax = pmax*2-a
    ans.append(pmax)

final_ans = []
prev = 0
for i in range(N+1):
  pmax = ans[N-i]
  final_ans.append(min(pmax,prev)+A[N-i])
  prev = final_ans[-1]

if final_ans[-1] != 1:
  print(-1)
  exit()
  
print(sum(final_ans))

Solution (Python):
import sys
N = int(input())
A = [int(c) for c in input().split()]
B = [0]*(N+1)
B[0] = 1
if A[0]>=1:
  if N==0 and A[0]==1:
    print(1)
  else:
    print(-1)
  sys.exit()
for i in range(1,N+1):
  B[i] = B[i-1]*2-A[i]
  if B[i]<0:
    print(-1)
    sys.exit()
ans = sum(A)
num = 0
for i in range(N,0,-1):
  num = min(num+A[i],B[i-1])
  ans += num
print(ans)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
L=[0]*(n+1)
L[0]=1
Chk=True
for i in range(n+1):
  if i==0:
    if A[i]>0:
      Chk=False
      break
  elif i<n:
    if L[i-1]*2<=A[i]:
      Chk=False
      break
    else:
      L[i]=L[i-1]*2-A[i]
  else:
    L[i]=L[i-1]*2

if L[-1]<A[-1]:
  Chk=False
else:
  L[-1]=0
  ans=A[-1]
  for i in range(n)[::-1]:
    if A[i+1]+L[i+1]<L[i]:
      L[i]=A[i+1]+L[i+1]
    ans+=L[i]+A[i]


if n==0 and A==[1]:
  print(1)
else:
  if Chk:
    print(ans)
  else:
    print(-1)

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

nodes = []
if a[0] > 0:
    if a[0] == 1 and n == 0: print(1)
    else: print(-1)
    exit()
else:
    nodes.append(1)
if a[-1] > 2 ** n:
    print(-1)
    exit()


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


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

print(sum(a) + sum(nodes))

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()

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

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

    node[N] = 0
    for i in range(N-1,-1,-1):
        if node[i+1]+A[i+1] > node[i] * 2:
            print(-1)
            return
        node[i] = min(node[i+1]+A[i+1],node[i])

    print(sum(node)+sum(A))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
flg = 1
if n == 0 and a[0] != 1:
    print(-1)
elif n == 0:
    print(1)
else:
    acc = [0]
    for i in range(n,-1,-1):
        acc.append(acc[-1] + a[i])
    ans = 0
    s = 1

    for i in range(n+1):
        if i != 0:
            s = min(s*2,acc[-i-1])
        ans += s
        s -= a[i]
        if s < 0:
            flg = 0
        
    if flg:
        print(ans)
    else:
        print(-1)

Solution (Python):
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:
    rest = [1]
    for i in range(1, N+1):
        rest.append(min(rest[i-1]*2 - A[i], 10**13))
    ans, cnodes = A[N], A[N]
    for i in range(N-1, -1, -1):
        if cnodes//2 + cnodes%2 > rest[i]:
            print(-1)
            exit()
        else:
            cnodes = min(cnodes, rest[i]) + A[i]
            ans += cnodes
    print(ans)

Solution (Python):
import copy

n = int(input())

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

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

for i in range(n + 1):
    if i == 0:
        down_max[0] = 1
    else:
        down_max[i] = 2 * (down_max[i - 1] - a_i[i - 1])

answer = 0
now_point_number = 0
before_point_number = 0
cant_make = False

for i in range(n + 1):
    depth_index = - i - 1
    if i == 0:
        now_point_number = a_i[depth_index]
    else:
        if before_point_number // 2 + before_point_number % 2 + a_i[depth_index] > down_max[depth_index]:
            cant_make = True
            break
        else:
            now_point_number = min(down_max[depth_index], before_point_number + a_i[depth_index])
    answer += now_point_number
    before_point_number = copy.copy(now_point_number)

if n == 0 and a_i[0] != 1:
    cant_make = True

if cant_make:
    print(-1)
else:
    print(answer)

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

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

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

INF = 10**15

cond = [1]
m = INF
for a in A[1:]:
    c = min(INF, cond[-1]*2-a)
    if c<0:
        print(-1)
        exit()
    cond.append(c)

ans = 0
node = 0
for n in range(N, -1, -1):
    n1 = A[n]
    n2 = min(cond[n], node)
    node = n1 + n2
    ans += node

print(ans)

Solution (Python):


LI = lambda: list(map(int, input().split()))


N = int(input())
A = LI()


def main():
    if A[0] >= 2:
        print(-1)
        return
    l, r = [None] * (N + 1), [None] * (N + 1)
    l[0], r[0] = 1, 1
    l[-1], r[-1] = A[-1], A[-1]
    for i in range(N - 1, 0, -1):
        l[i] = (l[i + 1] + 1) // 2 + A[i]
        r[i] = r[i + 1] + A[i]
    
    ans = 1
    x = 1
    for i in range(1, N + 1):
        x -= A[i - 1]
        if x < 0:
            print(-1)
            return
        s = max(x, l[i])
        t = min(2 * x, r[i])
        if s > t:
            print(-1)
            return
        x = t
        ans += t
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(raw_input())
ais = map(int, raw_input().split(' '))

def f(ais,n):
	q = 1 
	r = 0
	h = {}
	for depth,nl in enumerate(ais):
		if nl > q: return -1
		elif nl == q:
			if depth < n: return -1
			q -= nl
		elif nl < q:
			q -= nl
		
		h[depth] = q
		if depth < n: q *= 2
	
	internal = 0
	for j in range(len(ais)-1, 0, -1):
		r += ais[j] + internal
		internal = min(h[j - 1], ais[j] + internal) 
	return r + 1


print f(ais,n)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
num_node=[1]*(N+1)
for i in range(1,N+1):
    tmp=2*(num_node[i-1]-A[i-1])
    if tmp<0:
        print(-1)
        exit()
    num_node[i]=tmp

tmp=2*(num_node[N]-A[N])
if tmp<0:
    print(-1)
    exit()

num_node[-1]=A[N]
for i in range(N-1,-1,-1):
    tmp=num_node[i+1]
    tmp+=A[i]
    if tmp<=num_node[i]:
        num_node[i]=tmp

print(sum(num_node))

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

B = [1]
for i in range(n):
    B.append((B[i]-A[i])*2)

C = [A[n]]

for i, s in enumerate(B):
    if i == len(B)-1:
        a = 1
    elif B[i] <= 0:
        print(-1)
        exit()
if B[-1]-A[n] < 0:
    print(-1)
    exit()

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

num = 0
frag = 0
for i in range(n):
    if B[i] >= C[i]:
        frag = 1
    if frag == 0:
        num += B[i]
    else:
        num += C[i]
num += C[n]
print(num)