Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################
 
#####ide_ele#####
ide_ele = 10**9
#################
 
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
 
    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1
 
    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele
 
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


N, Q = map(int, input().split())



ans = (N-2)**2
yoko = [N-2 for _ in range(N-2)]
tate = [N-2 for _ in range(N-2)] 
yoko = SegTree(yoko, segfunc, ide_ele)
tate = SegTree(tate, segfunc, ide_ele)
miny = N-2
minx = N-2
for k in range(Q):
	n, x = map(int, input().split())
	if n == 1:
		y = x -2
		if y < miny:
			ans -= minx
			miny = y
			yoko.update(min(minx, N-3), miny)
		else:
			ans -= tate.query(y, N-1)
	else:
		x = x - 2
		if x < minx:
			ans -= miny
			minx = x
			tate.update(min(miny, N-3), minx)
		else:
			ans -= yoko.query(x, N-1)
print(ans)


Fixed submission:
S = input()
if S[-1] != 's':
	print(S + 's')
else:
	print(S+'es')
Buggy python submission (verdict: Runtime Error):
#from collections import deque
#from heapq import heapify, heappop, heappush
#from bisect import insort
#from math import gcd
#mod = 10**9 + 7
N = int(input())
#N, K = map(int, input().split())
#A = list(map(int, input().split()))
flag1 = False
flag2 = False
flag3 = False
c, d = map(int, input().split())
if c == d:
	flag1 = True
c, d = map(int, input().split())
if c == d:
	flag2 = True
c, d = map(int, input().split())
if c == d:
	flag3 = True

k = 3
while k < N:
	if flag1 and flag2 and flag3:
		break
	k += 1
	c, d = map(int, input().split())
	flag1 = flag2
	flag2 = flag3
	if c == d:
		flag3 = True
	else:
		flag3 = False
		

#ans = 0
#print(ans)
#print('Yes')
if flag1 and flag2 and flag3:
	print('Yes')
else:
	print('No')#from collections import deque
#from heapq import heapify, heappop, heappush
#from bisect import insort
#from math import gcd
#mod = 10**9 + 7
N = int(input())
#N, K = map(int, input().split())
#A = list(map(int, input().split()))
flag1 = False
flag2 = False
flag3 = False
c, d = map(int, input().split())
if c == d:
	flag1 = True
c, d = map(int, input().split())
if c == d:
	flag2 = True
c, d = map(int, input().split())
if c == d:
	flag3 = True

k = 3
while k < N:
	if flag1 and flag2 and flag3:
		break
	k += 1
	c, d = map(int, input().split())
	flag1 = flag2
	flag2 = flag3
	if c == d:
		flag3 = True
	else:
		flag3 = False
		

#ans = 0
#print(ans)
#print('Yes')
if flag1 and flag2 and flag3:
	print('Yes')
else:
	print('No')

Fixed submission:
#from collections import deque
#from heapq import heapify, heappop, heappush
#from bisect import insort
#from math import gcd
#mod = 10**9 + 7
N = int(input())
#N, K = map(int, input().split())
#A = list(map(int, input().split()))
flag1 = False
flag2 = False
flag3 = False
c, d = map(int, input().split())
if c == d:
	flag1 = True
c, d = map(int, input().split())
if c == d:
	flag2 = True
c, d = map(int, input().split())
if c == d:
	flag3 = True

k = 3
while k < N:
	if flag1 and flag2 and flag3:
		break
	k += 1
	c, d = map(int, input().split())
	flag1 = flag2
	flag2 = flag3
	if c == d:
		flag3 = True
	else:
		flag3 = False
		

#ans = 0
#print(ans)
#print('Yes')
if flag1 and flag2 and flag3:
	print('Yes')
else:
	print('No')
Buggy python submission (verdict: Runtime Error):
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')


Fixed submission:
import sys
sys.setrecursionlimit(2*10**9)

N, M = map(int, input().split())
friends = [[] for _ in range(N)]
for k in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  friends[A].append(B)
  friends[B].append(A)
group = []
sgn = [0 for _ in range(N)] #0なら未所属
def make_group(person, groupnum):
  sgn[person] = 1
  for f in friends[person]:
    if sgn[f] == 0:
      group[groupnum].append(f)
      make_group(f, groupnum)
  return None

c = 0
for k in range(N):
  if sgn[k] == 0:
    group.append([k])
    make_group(k, c)
    c += 1
ans = 0
for g in group:
  ans = max(len(g), ans)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
for k in range(N):
  P[k] -= 1
scorelist = []
roop = []
now = 0
visited = [-1 for _ in range(N)]
for k in range(N):
  now = k
  if visited[now] == -1:
    roop.append([])
    scorelist.append([])
    start = 0 + now
    while visited[start] == -1:
      roop[-1].append(start)
      visited[start] = 1 
      start = P[start]
      scorelist[-1].append(C[start])
    scorelist[-1] = scorelist[-1] + scorelist[-1]
    
#print(roop)
#print(scorelist)

ans = - float('inf')
for l in range(len(roop)):
  #print(scorelist[l][:len(roop[l])])
  Q = K // len(roop[l])
  R = K % len(roop[l])
  if Q > 0 and R == 0:
    Q -= 1
    R = len(roop[l]) 
  #print(Q, R)
  if sum(scorelist[l][:len(roop[l])]) > 0:
    basis = sum(scorelist[l][:len(roop[l])])*Q
  else:
    basis = 0
  #print(basis)
  adv = - float('inf')
  for k in range(len(roop[l])):
    for j in range(k, k + R):
      adv = max(adv, sum(scorelist[l][k:j+1]))
  ans = max(ans, basis + adv)

print(ans)

Fixed submission:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
for k in range(N):
  P[k] -= 1
scorelist = []
roop = []
now = 0
visited = [-1 for _ in range(N)]
for k in range(N):
  now = k
  if visited[now] == -1:
    roop.append([])
    scorelist.append([])
    start = 0 + now
    while visited[start] == -1:
      roop[-1].append(start)
      visited[start] = 1 
      start = P[start]
      scorelist[-1].append(C[start])
    scorelist[-1] = scorelist[-1] + scorelist[-1] + scorelist[-1]
    
#print(roop)
#print(scorelist)

ans = - float('inf')
for l in range(len(roop)):
  #print(scorelist[l][:len(roop[l])])
  Q = K // len(roop[l])
  R = K % len(roop[l])
  if Q > 0:
    Q -= 1
    R += len(roop[l]) 
  #print(Q, R)
  if sum(scorelist[l][:len(roop[l])]) > 0:
    basis = sum(scorelist[l][:len(roop[l])])*Q
  else:
    basis = 0
  #print(basis)
  advlist = -float('inf')
  for k in range(len(roop[l])):
    adv = 0
    for j in range(k, k + R):
      adv += scorelist[l][j]
      advlist  = max(advlist, adv) 
  ans = max(ans, basis + advlist)

print(ans)
Buggy python submission (verdict: Runtime Error):
N , K = map(int, input().split())
A =list(map(int, input().split()))
mod = 10**9 + 7
count =0
for k in range(len(A)):
    if A[k] == 0:
        count +=1
        A[k] = float("inf")
if N-count < K:
    print(0)
    exit()
A.sort()
A = A[:N-count]
A.sort(reverse=True)
#print(A)
ans = 1
plus = 0
minus = -1
countp = 0
countm = 0
if A[0] >0:
    for k in range(K):
        if abs(A[plus]) >= abs(A[minus]):
            ans = ans*A[plus]%mod
            plus+=1
        else:
            ans = ans*A[minus]%mod
            if A[minus] <0:
                lasm = 0+minus
            minus-=1
            
    if minus%2 == 1:
        print(ans%mod)
    else:
        print(ans//A[lasm]*max(A[plus], A[minus])%mod)
else:
    for k in range(K):
        ans = ans*A[k]%mod
    print(ans%mod)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0 
if N %2 ==1:
    ans += A[0]
    k = 0
    for j in range(1, N//2):
        k += 1
        ans += 2*A[k]
    ans += A[k+1]
if N%2 == 0:
    ans += A[0]
    k = 0
    for j in range(1, N//2):
        k += 1
        ans += 2*A[k]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
mod = 10**9 + 7

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, M + 1):
  fact.append((fact[-1] * i) % mod)
  inv.append((-inv[mod % i] * (mod // i)) % mod)
  factinv.append((factinv[-1] * inv[-1]) % mod)

ans = fact[M]*factinv[M-N]%mod #Aの選び方

y = [fact[M-N]]
x = factinv[N]*y[-1]%mod
for k in range(1, N):
  minus = 0
  for j in range(k):
    minus = (minus+fact[k]*factinv[k-j]%mod*factinv[j]%mod)%mod
  y.append((fact[M-N+k] - minus)%mod)
  x = (x+y[-1]*factinv[k]%mod*factinv[N-k]%mod)%mod
x = x*fact[N]%mod*factinv[M-N]%mod
print(ans*(ans-x)%mod)

Fixed submission:
N, M = map(int, input().split())
mod = 10**9 + 7

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, M + 1):
  fact.append((fact[-1] * i) % mod)
  inv.append((-inv[mod % i] * (mod // i)) % mod)
  factinv.append((factinv[-1] * inv[-1]) % mod)

ans = 0
for k in range(N+1):
  if k%2 == 0:
    ans = (ans+factinv[N-k]*factinv[k]%mod*fact[M-k]%mod)%mod
  else:
    ans = (ans-factinv[N-k]*factinv[k]%mod*fact[M-k]%mod)%mod
ans = ans*fact[N]%mod*fact[M]%mod*factinv[M-N]%mod*factinv[M-N]%mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
S = input()
S = len(S)


mod = 10**9 + 7

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

from collections import deque

kaijou = 1
fact = [1]
for k in range(1, K + S+1):
  kaijou = kaijou * k % mod
  fact.append(kaijou)

fact_k = deque(fact[:K+1])
fact_ks = deque(fact[S-1:])


list26 = deque([1])
list25 = deque([1])
now26 = 26
now25 = 25
for k in range(K):
  list25.append(now25)
  list26.append(now26)
  now25 = now25*25%mod
  now26 = now26*26%mod


ans = 0
for k in range(K+1):
  now = list26.pop()
  now = now * list25.popleft() % mod
  now = now * fact_ks.popleft() % mod
  now = now * modinv(fact_k.popleft()) %mod
  ans += now
  ans %= mod


ans *= modinv(fact[S-1])
ans %= mod
print(ans)


Fixed submission:
K = int(input())
S = input()
S = len(S)


mod = 10**9 + 7

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

from collections import deque

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, K + S + 1):
  fact.append((fact[-1] * i) % mod)
  if i < K+2:
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

factinv_k = deque(factinv[:K+1])
fact_ks = deque(fact[S-1:])


list26 = deque([1])
list25 = deque([1])
now26 = 26
now25 = 25
for k in range(K):
  list25.append(now25)
  list26.append(now26)
  now25 = now25*25%mod
  now26 = now26*26%mod


ans = 0
for k in range(K+1):
  now = list26.pop()
  now = now * list25.popleft() % mod
  now = now * fact_ks.popleft() % mod
  now = now * factinv_k.popleft() %mod
  ans += now
  ans %= mod


ans *= modinv(fact[S-1])
ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c=0
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        c+=1
        if k <len(A)-2:
            if A[k+1] != A[k+2]:
                del A[k+1]
                A.insert(0,0)
                c+=1
        else:
            del A[k+1]
            A.insert(0,0)
            c+=1
del A[:c]
if len(A)>0:
    saidai = A[-1]
else:
    saidai=0
print(A)
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        count+=1
        for j in range(A[k], saidai+1, A[k]):
            foo[j] = 1
print(count) 

Fixed submission:
A = list(map(int, input().split()))
for k in range(5):
    if A[k] == 0:
        print(k+1)
        break
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c= 0
if N>1:
    if A[0]%A[1] >0:
        count+=1

for k in range(1, len(A)):
    if k<N-1:
        if A[k] == A[k+1]:
            continue
    for j in range(c, k):
        if A[k]%A[j] ==0:
            del A[k]
            A.insert(0, 0)
            c +=1
            break
    else:
        count +=1
        #print(A[k])

    
if N ==1:
    count = 1
print(count)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c=0
"""
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        c+=1
        if k <len(A)-2:
            if A[k+1] != A[k+2]:
                del A[k+1]
                A.insert(0,0)
                c+=1
        else:
            del A[k+1]
            A.insert(0,0)
            c+=1
del A[:c]
if len(A)>0:
    saidai = A[-1]
else:
    saidai=0
#print(A)
"""
saidai = A[-1]
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        for j in range(A[k], saidai+1, A[k]):
            foo[j] = 1
        if k < len(A)-1:
            if A[k] == A[k+1]:
                continue
        if 0 < k < len(A):
            if A[k] == A[k-1]:
                continue
        count+=1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()

for k in range(1, N):
    if k<N-1:
        if A[k] == A[k+1]:
            continue
    for j in range(k):
        if A[k]%A[j] ==0:
            break
    else:
        count +=1
        #print(A[k])
if N>1:
    if A[0]%A[1] >0:
        count+=1
    
if N ==1:
    count = 1
print(count)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c=0
"""
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        c+=1
        if k <len(A)-2:
            if A[k+1] != A[k+2]:
                del A[k+1]
                A.insert(0,0)
                c+=1
        else:
            del A[k+1]
            A.insert(0,0)
            c+=1
del A[:c]
if len(A)>0:
    saidai = A[-1]
else:
    saidai=0
#print(A)
"""
saidai = A[-1]
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        for j in range(A[k], saidai+1, A[k]):
            foo[j] = 1
        if k < len(A)-1:
            if A[k] == A[k+1]:
                continue
        if 0 < k < len(A):
            if A[k] == A[k-1]:
                continue
        count+=1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [-1 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    #process1 追加する
    if item + a <= S:
      if nextdp[item+a] == -1:
        nextvisit.append(item+a)
        nextdp[item+a] = 0
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    #process2 追加しない
    nextdp[item] += dp[item]
    nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(max(dp[-1], 0))


Fixed submission:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    #process1
    if item + a <= S:
      if nextdp[item+a] == 0:
        nextvisit.append(item+a)
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    #process2
    if item <= S:
      nextdp[item] += dp[item]
      nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
conunter = [[0] for _ in range(S+1)] #counter[num][numに必要な要素数] = numの組み合わせ数
visited = [0]
conunter[0] = [1]

for k in range(N):
  a = A[k]
  new_count = []
  new_visit = []
  for item in visited:
    if item +a > S:
      continue
    if len(conunter[item+a]) == 1:
      new_visit.append(item+a)
    new_count.append((item + a, tuple(conunter[item])))
  visited.extend(new_visit)
  for new in new_count:
    for k in range(len(new[1])):
      plus = new[1][k]
      if len(conunter[new[0]]) < k+2:
        conunter[new[0]].append(plus)
      else:
        conunter[new[0]][k+1] += plus


two = [1]
for k in range(N):
  two.append(two[-1]*2%mod)


foo = conunter[-1]
ans = 0
for k in range(1, len(foo)): 
  ans = (ans + foo[k]*two[N-k])%mod
print(ans)


Fixed submission:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    #process1
    if item + a <= S:
      if nextdp[item+a] == 0:
        nextvisit.append(item+a)
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    #process2
    if item <= S:
      nextdp[item] += dp[item]
      nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
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):
    #print(capacity)
    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
        for m in range(N+1):
            ans[m] = min(capacity[m], sum(A[m:N+1]))
        print(sum(ans))





Fixed submission:
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):
    #print(capacity)
    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))

Buggy python submission (verdict: Time Limit Exceeded):
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):
    #print(capacity)
    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
        for j in range(N+1):
            for m in range(j+1):
                ans[m] = min(capacity[m], ans[m] + A[j])
        print(sum(ans))





Fixed submission:
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):
    #print(capacity)
    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))