Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a =list(map(int,input().split()))
total = 1
i = 0
while i <n:
    if 0 in a:
        total =0 
        break
    
    total *= int(a[i])
    if total >10**18:
        total = '-1'
        break
    i += 1
    
print(total)

Fixed submission:
a = int(input())
li = list(map(int,input().split()))
total = 1
i = 1
for i in range(a):
    total = total*li[i]
    if total > 1000000000000000000:
        total = -1
        break
for i in range(a):
    if li[i] == 0:
        total = 0
 
print(total)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a_list =input().split()
total = 1
for i in range(n):
    total *= int(a_list[i])
if total > 10**18:
    print(-1)
else:
    print(total)

Fixed submission:
a = int(input())
li = list(map(int,input().split()))
total = 1
i = 1
for i in range(a):
    total = total*li[i]
    if total > 1000000000000000000:
        total = -1
        break
for i in range(a):
    if li[i] == 0:
        total = 0
 
print(total)
Buggy python submission (verdict: Runtime Error):
import math
a,b =input().split()
a = int(a)
b = float((int(int(b)*100))/100)
c = math.floor(a*b)
print(c)

Fixed submission:
a,b = input().split()
a = int(a)
b = int(b.replace('.',''))
print(a*b//100)

Buggy python submission (verdict: Runtime Error):
import math
a,b =input().split()
a = int(a)
b = float((int(b*100))/100)
c = math.floor(a*b)
print(c)

Fixed submission:
a,b = input().split()
a = int(a)
b = int(b.replace('.',''))
print(a*b//100)
Buggy python submission (verdict: Runtime Error):
a,b,h,m = map(int,input().split())
import math
alp = 0.5*(h*60+m)/180*math.pi
be = 6*m/180*math.pi
if alp >=be:
    if alp-be < math.pi: 
        l = (a**2+b**2 - 2*a*b*math.cos(alp - be))**(1/2)
    else:
        l = (a**2+b**2 + 2*a*b*math.cos(alp - be))**(1/2)
else:
    if be-alp < math.pi:
        l = (a**2+b**2 - 2*a*b*math.cos(be - alp))**(1/2)
    else:
        l = (a**2+b**2 + 2*a*b*math.cos(be - alp))**(1/2)
print(l)

Fixed submission:
n = int(input())
p = n%10
hon = [2,4,5,7,9]
pon = [0,1,6,8]
if p in hon:
    print('hon')
elif p in pon:
    print('pon')
else:
    print('bon')
Buggy python submission (verdict: Runtime Error):
import numpy as np
n,m,x = map(int,input().split())
l = []
for i in range(n):
    l.append(np.array(input().split(),dtype=int)) 
import itertools
num = [i for i in range(n)]
min = 100000000000001
k = 1
while k <n+1:
    a = list(itertools.combinations(num, k))
    for i in range(len(a)):
        total =np.zeros(m+1,dtype=int)
        for j in range(len(a[i])):
            total +=l[a[i][j]]
        if np.sum(np.where(total < x)[0]) <=0:
            if min > total[0]:
                min = total[0]
                k = n+2
    k +=1
if min == 100000000000001:
  print(-1)
else:
  print(min)

Fixed submission:
s = input()
t = input()
if t.find(s) == 0 and len(t)-len(s) == 1:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = input().split()
b = [0]*n
d = {}
ind = 1
num = 0
loop = 1
while num == k:
    if b[ind-1] == 0:
        b[ind-1] = -1
        d[ind] = num
        num += 1
        ind = int(a[ind-1])
    else:
        loop = num-d[ind]
        sup = d[ind]
        break

if k-sup >=0:
    for i in range((k-sup)%loop):
        ind = int(a[ind-1])

print(ind)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
next = 1
List = [-1]*N
 
for i in range(K):
    if List[next-1] == -1:
        List[next-1] = i
        next = A[next-1]
 
    else:
        loop = i - List[next-1]
        afterloop = (K-(i-loop))%loop
        print(List.index((i-loop) + afterloop)+1)
        exit()
 
print(next)

Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = input().split()
b = [0]*n
d = {}
ind = 1
num = 0
while True:
    if b[ind-1] == 0:
        b[ind-1] = -1
        d[ind] = num
        num += 1
        ind = int(a[ind-1])
    else:
        loop = num-d[ind]
        sup = d[ind]
        break


for i in range((k-sup)%loop):
    ind = int(a[ind-1])
print(int(a[ind]))

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
next = 1
List = [-1]*N
 
for i in range(K):
    if List[next-1] == -1:
        List[next-1] = i
        next = A[next-1]
 
    else:
        loop = i - List[next-1]
        afterloop = (K-(i-loop))%loop
        print(List.index((i-loop) + afterloop)+1)
        exit()
 
print(next)
Buggy python submission (verdict: Runtime Error):
import itertools
n,m,q = map(int,input().split())
group = []
for i in range(q):
  w,x,y,z = map(int,input().split())
  v = (w,x,y,z)
  group.append(v)
#groupに(a,b,c,d)がタプルで入っている
max_value = max(group[i][3] for i in range(len(group)))

#Aの配列を試す

l = [i for i in range(1,m+1)]
h = itertools.combinations_with_replacement(l,n)
array =[]

for v in h:
    array.append(v)
#arrayが全ての配列になった


for j in range(len(array)):
  total = 0
  for i in range(q):
    if array[j][group[i][1]-1] - array[j][group[i][0]-1] == group[i][2]:
      total += group[i][3]
  if total >= max_value:
    max_value = total  

print(max_value)

Fixed submission:
k = int(input())
a,b = map(int,input().split())
c =0
for i in range(1,int(b/k)+1):
    if a <= i*k <= b:
        c = 1
        break
if c ==1:
    print('OK')
else:
    print('NG')
Buggy python submission (verdict: Runtime Error):
# -*- encode utf-8 -*-
#羊の数と狼の数を入力
S,W = int(input())
狼の数が羊の数以上のとき、羊は狼に襲われてしまいます。
if 2W >= S:
	print(unsafe)
else:
	print(safe)


Fixed submission:
s,w = input().split()
if int(w) >= int(s):
  print('unsafe')
else:
  print('safe')
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    b = [a[i] for i in range(n + 1)]
    for i in reversed(range(0, n)):
        b[i] += b[i + 1]
    result = a[n]
    d = 0
    for i in range(n):
        d = 2 * d + a[i]
        if 2 ** i - d < 0:
            print(-1)
            return
        result += min(2 ** i - d, b[i + 1]) + a[i]
    d = 2 * d + a[n]
    if 2 ** n - d < 0:
        print(-1)
        return
    print(result)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    b = [a[i] for i in range(n + 1)]
    for i in reversed(range(0, n)):
        b[i] += b[i + 1]
    pow2 = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        pow2[i] = 2 * pow2[i - 1]
    result = a[n]
    d = 0
    for i in range(n):
        d = 2 * d + a[i]
        if pow2[i] - d < 0:
            print(-1)
            return
        result += min(pow2[i] - d, b[i + 1]) + a[i]
    d = 2 * d + a[n]
    if pow2[n] - d < 0:
        print(-1)
        return
    print(result)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        # 先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
            else:
                ans += bit_acc[j] * (2 ** (leng - j - 1))
            ans %= mod
    print((ans * 500000004) % mod)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        # 先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    p = [pow(2, (leng - j - 1), mod) for j in range(leng)]
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N = int(input())
X = input().strip()

if not '1' in X:
    for i in range(N):
        print(0)
    exit()

M = 2*10**5+ 1
pc = [0]*(M+2)
for i in range(1,M+2):
    j = i
    t = 0
    while i > 0:
        k = bin(i).count('1')
        i %= k
        t += 1
    pc[j] = t

X1 = X.count('1')
X0 = N - X1

Rp1 = []
Rm1 = []
Bp1 = []
Bm1 = []
for i, x in enumerate(list(X[::-1])):
    tp1 = pow(2,i,X1+1)
    tm1 = pow(2,i,X1-1)
    Bp1.append(tp1)
    Bm1.append(tm1)
    if x == '1':
        Rp1.append(tp1)
        Rm1.append(tm1)
    else:
        Rp1.append(0)
        Rm1.append(0)

basep1 = sum(Rp1)
basem1 = sum(Rm1)
Rp1 = Rp1[::-1]
Rm1 = Rm1[::-1]
Bp1 = Bp1[::-1]
Bm1 = Bm1[::-1]

#print("base",basep1)
#print("base",basem1)
for bp1,bm1,x in zip(Bp1,Bm1,X):
    if x == '1':
        t = basem1 - bm1
        MOD = X1 - 1
    else:
        t = basep1 + bp1
        MOD = X1 + 1

    #print("x",x,"t",t)
    #print(t % MOD,MOD)
    print(pc[t % MOD] + 1)




Fixed submission:
import sys
input = sys.stdin.readline
N = int(input())
X = input().strip()

def solve(N,X):
    if not '1' in X:
        for i in range(N):
            print(1)
        exit()

    def popcount(n):
        t = 0
        while n > 0:
            k = bin(n).count('1')
            n %= k
            t += 1
        return t

    X1 = X.count('1')

    Rp1 = []
    Rm1 = []
    Bp1 = []
    Bm1 = []

    for i, x in enumerate(list(X[::-1])):
        tp1 = pow(2,i,X1+1)
        if X1-1 > 0:
            tm1 = pow(2,i,X1-1)
        else:
            tm1 = 0
        Bp1.append(tp1)
        Bm1.append(tm1)
        if x == '1':
            Rp1.append(tp1)
            Rm1.append(tm1)
        else:
            Rp1.append(0)
            Rm1.append(0)

    basep1 = sum(Rp1) % (X1+1)
    if X1-1 > 0:
        basem1 = sum(Rm1) % (X1-1)
    else:
        basem1 = 0
    Rp1 = Rp1[::-1]
    Rm1 = Rm1[::-1]
    Bp1 = Bp1[::-1]
    Bm1 = Bm1[::-1]

    #print("base",basep1)
    #print("base",basem1)
    for bp1,bm1,x in zip(Bp1,Bm1,X):
        if x == '1':
            t = basem1 - bm1
            MOD = X1 - 1
            if MOD <= 0:
                print(0)
                continue
        else:
            t = basep1 + bp1
            MOD = X1 + 1
        #print("x",x,"t",t)
        #print(t % MOD,MOD)
        print(popcount(t % MOD) + 1)

solve(N,X)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

r = reduce(lambda x,y : x^y , A[2:],0)

a,b = A[:2]

def answer(ta,tb,tr):
    for i in range(ta):
        if (ta-i)^(tb+i) == tr:
            ans = i
            break
    else:
        ans = -1
    return ans

def solve(a,b,r):
    orga = a

    ans = 0
    l = max(map(lambda x : len(bin(x)), [a,b,r])) - 2
    cand = {(a,b,r):0}
    for i in range(l):
        temp = defaultdict(lambda : 10**10)
        for (a,b,r),s in cand.items():
            x,y,z = a%2,b%2,r%2
            if not x^y == z:
                continue
            else:
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
                a -= 1
                b += 1
                if a < 0:
                    continue
                s += (1<<i)
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
        cand = temp

    if not (0,0,0) in cand:
        ans = -1
    else:
        ans = cand[(0,0,0)]
        if ans == orga:
            ans = -1
    return ans

print(answer(a,b,r))


Fixed submission:
from functools import reduce
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

r = reduce(lambda x,y : x^y , A[2:],0)

a,b = A[:2]

def answer(ta,tb,tr):
    for i in range(ta):
        if (ta-i)^(tb+i) == tr:
            ans = i
            break
    else:
        ans = -1
    return ans

def solve(a,b,r):
    orga = a

    ans = 0
    l = max(map(lambda x : len(bin(x)), [a,b,r])) - 2
    cand = {(a,b,r):0}
    for i in range(l):
        temp = defaultdict(lambda : 10**20)
        for (a,b,r),s in cand.items():
            x,y,z = a%2,b%2,r%2
            if not x^y == z:
                continue
            else:
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
                a -= 1
                b += 1
                if a < 0:
                    continue
                s += (1<<i)
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
        cand = temp

    if not (0,0,0) in cand:
        ans = -1
    else:
        ans = cand[(0,0,0)]
        if ans == orga:
            ans = -1
    return ans

print(solve(a,b,r))
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7
K = int(input())
S = input()

A = list(map(ord,S))

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

M = K+len(S)
dp = dpinit((M+1,len(S)+1))

dp[0][0] = 1

for i in range(1,M+1):
    for j in range(len(S)+1):
        dp[i][j] += dp[i-1][j]*25
        dp[i][j] %= MOD
        if j+1 <= len(S):
            dp[i][j+1] += dp[i-1][j]
            dp[i][j+1] %= MOD
    dp[i][len(S)] += dp[i-1][len(S)]
    dp[i][len(S)] %= MOD

print(dp[M][len(S)])




Fixed submission:
MOD = 10**9 + 7
K = int(input())
S = input()


N = len(S)
M = K+N
s = [pow(26,K,MOD)]

r26 = pow(26,MOD-2,MOD)
for i in range(1,K+1):
    t = s[-1]
    t *= r26
    t *= 25
    t *= N+i-1
    t *= pow(i,MOD-2,MOD)
    t %= MOD
    s.append(t)


ans = sum(s) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

MOD = 998244353
A,B,C,D= map(int,input().split())
#A,B,C,D = 1,1,100,100

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

memo = dpinit((C+1,D+1))
memo[A][B] = 1
for Y in range(A,C+1):
    memo[Y][1] = 1
for X in range(B,D+1):
    memo[1][X] = 1

def cnt(C,D):
    if memo[C][D] != 0:
        return memo[C][D]
    res = 0
    if C > A:
        res += (D * cnt(C-1,D) % MOD)
    if D > B:
        res += (C * cnt(C,D-1) % MOD)
    if C > A and D > B:
        res -= (cnt(C-1,D-1)*(C-1)*(D-1) % MOD)
    res %= MOD
    memo[C][D] = res 
    return res

print(cnt(C,D))






Fixed submission:
import sys
sys.setrecursionlimit(10**7)

MOD = 998244353
A,B,C,D= map(int,input().split())
#A,B,C,D = 1,1,3000,3000

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

memo = dpinit((C+1,D+1))

memo[A][B] = 1
for Y in range(A,C+1):
    memo[Y][B] = pow(B,Y-A,MOD)
for X in range(B,D+1):
    memo[A][X] = pow(A,X-B,MOD)

for y in range(A+1,C+1):
    for x in range(B+1,D+1):
        memo[y][x] = (x*memo[y-1][x] + y*memo[y][x-1] - (x-1)*(y-1)*memo[y-1][x-1]) % MOD

print(memo[C][D])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

MOD = 998244353
A,B,C,D= map(int,input().split())

memo = {(A,B):1}
for Y in range(A,C+1):
    memo[(Y,1)] = 1
for X in range(B,D+1):
    memo[(1,X)] = 1

def cnt(C,D):
    if (C,D) in memo:
        return memo[(C,D)]
    res = 0
    if C > A:
        res += D * cnt(C-1,D)
    if D > B:
        res += C * cnt(C,D-1)
    if C > A and D > B:
        res -= cnt(C-1,D-1)*(C-1)*(D-1)
    res %= MOD
    memo[(C,D)] = res 
    return res

print(cnt(C,D))






Fixed submission:
import sys
sys.setrecursionlimit(10**7)

MOD = 998244353
A,B,C,D= map(int,input().split())
#A,B,C,D = 1,1,3000,3000

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

memo = dpinit((C+1,D+1))

memo[A][B] = 1
for Y in range(A,C+1):
    memo[Y][B] = pow(B,Y-A,MOD)
for X in range(B,D+1):
    memo[A][X] = pow(A,X-B,MOD)

for y in range(A+1,C+1):
    for x in range(B+1,D+1):
        memo[y][x] = (x*memo[y-1][x] + y*memo[y][x-1] - (x-1)*(y-1)*memo[y-1][x-1]) % MOD

print(memo[C][D])
Buggy python submission (verdict: Runtime Error):
from collections import deque,defaultdict
import bisect
N = int(input())
S = [input() for i in range(N)]

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i = i//2
            j = j//2
        return s

def bend(s):
    res = 0
    k = 0
    for th in s:
        if th == '(':
            k += 1
        else:
            k -= 1
        res = min(k,res)
    return res

LmR = defaultdict(list)
inf = -10**7
for s in S:
    LmR[bend(s)].append(s.count('(')-s.count(')'))
LmR = dict(LmR)
for k in LmR.keys():
    LmR[k].append(inf)
    LmR[k].sort(reverse=True)
    LmR[k] = deque(LmR[k])

keys = sorted(LmR.keys())
nk = len(keys)

comp = {k:i for i,k in enumerate(keys)}
seg = SegmentTree([(LmR[k].popleft(),k) for k in keys], lambda x,y : (x if x[0] > y[0] else y), (inf,inf))

cumsum = 0
for i in range(N):
    ind = bisect.bisect_left(keys,-cumsum)
    m,n = seg.get(ind-1,nk)
    if n == inf:
        print('No')
        exit()
    if cumsum + n < 0:
        print('No')
        exit()
    cumsum += m
    new = LmR[n].popleft()
    seg.set(comp[n], (new,n))

if cumsum == 0:
    print('Yes')
else:
    print('No')


Fixed submission:
from collections import deque,defaultdict
import bisect
N = int(input())
S = [input() for i in range(N)]

def bend(s):
    res = 0
    k = 0
    for th in s:
        if th == '(':
            k += 1
        else:
            k -= 1
        res = min(k,res)
    return res

species = [(bend(s),s.count('(')-s.count(')')) for s in S]

ups = [(b,u) for b,u in species if u > 0]
flats = [(b,u) for b,u in species if u == 0]
downs = [(b,u) for b,u in species if u < 0]


ups.sort()
high = 0
for b,u in ups[::-1] + flats:
    if high + b < 0:
        print('No')
        exit()
    high += u

rdowns = [(b-u,-u) for b,u in downs]
rdowns.sort()
high2 = 0
for b,u in rdowns[::-1]:
    if high2 + b < 0:
        print('No')
        exit()
    high2 += u

if high == high2:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))

dp = [[-10**18 for i in range(N//2+1)] for j in range(N+1)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    high = min(N//2, i//2+10)
    low = max(0,i//2-10)
    for j in range(high,low,-1):
        dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i-1])

print(dp[N][N//2])



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

dp = [[-10**18 for i in range(N//2+1)] for j in range(2)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    high = min(N//2, i//2+10)
    low = max(0,i//2-10)
    for j in range(high,low,-1):
        dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1] + A[i-1])
print(dp[N%2][N//2])

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

dp = [[-10**18 for i in range(N//2+1)] for j in range(N+1)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    for j in range(N//2,0,-1):
        dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i-1])

print(dp[N][N//2])



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

dp = [[-10**18 for i in range(N//2+1)] for j in range(2)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    high = min(N//2, i//2+10)
    low = max(0,i//2-10)
    for j in range(high,low,-1):
        dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1] + A[i-1])
print(dp[N%2][N//2])
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from collections import defaultdict
N,X,Y= map(int,input().split())

ans = defaultdict(int)
for i, j in combinations(range(1,N+1),2):
    d = min(abs(i-j),abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
    ans[d] += 1

for i in range(1,N):
    print(ans[i])





Fixed submission:
from itertools import combinations
from collections import defaultdict
N,X,Y= map(int,input().split())

ans = defaultdict(int)
for i, j in combinations(range(1,N+1),2):
    d = min(abs(i-j),abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
    ans[d] += 1

for i in range(1,N):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int ,input().strip()))

def solve(A):
    A = [abs(x-y) for x,y in zip(A,A[1:])]
    n = len(A)
    coef = 1
    for i in range(n-1):
        coef = coef ^ (coef << 1)
    coef = map(int, bin(coef)[2:])
    if 1 in A:
        B = [x % 2 for x in A]
        ans = reduce(xor, starmap(mul, zip(B,coef)))
    else:
        B = [x // 2 for x in A]
        ans = reduce(xor, starmap(mul, zip(B,coef)))*2
    return ans 

print(solve(A))



Fixed submission:
import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int ,input().strip()))

A = [abs(x-y) for x,y in zip(A,A[1:])]
n = len(A)
# Lucas
coef = [((n-1)&k)==k for k in range(n)]
if 1 in A:
    B = [x % 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))
else:
    B = [x // 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))*2

print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int ,input().strip()))

def solve(A):
    A = [abs(x-y) for x,y in zip(A,A[1:])]
    n = len(A)
    coef = 1
    for i in range(n-1):
        coef = coef ^ (coef << 1)
    coef = map(int, bin(coef)[2:])
    if 1 in A:
        B = [x % 2 for x in A]
        ans = reduce(xor, starmap(mul, zip(B,coef)))
    else:
        B = [x // 2 for x in A]
        coef = [nCr(n-1,i) for i in range(n)]
        ans *= 2
    return ans 

print(solve(A))


Fixed submission:
import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int ,input().strip()))

A = [abs(x-y) for x,y in zip(A,A[1:])]
n = len(A)
# Lucas
coef = [((n-1)&k)==k for k in range(n)]
if 1 in A:
    B = [x % 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))
else:
    B = [x // 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))*2

print(ans)