CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    mod = 998244353
    s, k = input().split()
    k = int(k)
    n = len(s)

    one = s.count("1")

    cnt = 0
    zero_list = []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1

    z = 0
    mm = min(one, k)

    dp = [[0]*(one+1) for _ in [0]*(one+1)]
    dp[0][0] = 1

    for i in range(len(zero_list)):
        dp2 = [[0]*(mm+1) for _ in [0]*(one+1)]
        base = zero_list[i]
        # j:何個今までに入れたか
        for j in range(one+1):
            # l:何個入れるか
            for l in range(one+1-j):
                if l < z+base-j:
                    continue
                ml = max(l-base, 0)
                # p:これまでのペナルティ
                for p in range(min(one, k)+1):
                    q = p+ml
                    if q <= mm:
                        dp2[j+l][q] = (dp2[j+l][q]+dp[j][p]) % mod
                    else:
                        break
        z += base
        dp = dp2
    print((sum([sum(i) for i in dp]) % mod))


main()

# Optimized solution
def main():
    mod = 998244353
    s, k = input().split()
    k, n, one, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    mm = min(one-1, k)

    dp = [[0]*(mm+1) for _ in [0]*one]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*(mm+1) for _ in [0]*one]
        for j in range(one):
            for l in range(max(z+i-j, 0), one-j):
                ml = max(l-i, 0)
                for p in range(min(j, mm-ml)+1):
                    dp2[j+l][p+ml] = (dp2[j+l][p+ml]+dp[j][p]) % mod
        z += i
        dp = dp2
    print((sum([sum(i) for i in dp]) % mod))


main()
# Original solution
def main():
    mod = 998244353
    s, k = input().split()
    k, n, one, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    mm = min(one-1, k)
    ans = 0

    dp = [[0]*(mm+1) for _ in [0]*one]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*(mm+1) for _ in [0]*one]
        for j in range(one):
            for l in range(max(z+i-j, 0), one-j):
                ml = max(l-i, 0)
                for p in range(min(j, mm-ml)+1):
                    ans += 1
                    dp2[j+l][p+ml] = (dp2[j+l][p+ml]+dp[j][p]) % mod
        z += i
        dp = dp2
    print((sum([sum(i) for i in dp]) % mod))


main()


# Optimized solution
def main():
    mod = 998244353
    s, k = input().split()
    k, n, one, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    mm = min(one-1, k)

    dp = [[0]*(mm+1) for _ in [0]*one]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*(mm+1) for _ in [0]*one]
        for jl in range(z+i, one):
            for x in range(i, min(one, jl+1, mm+i+1)):
                dp2[jl][x-i] = (dp2[jl][x-i]+sum([dp[jl-x+p][p]
                                                  for p in range(min(one, x-i+1))])) % mod
            for p in range(min(one, mm+1)):
                dp2[jl][p] = (dp2[jl][p]+sum([dp[jl-l][p]
                                              for l in range(min(one, i, jl-p+1))])) % mod
        z += i
        dp = dp2
    print((sum([sum(i) for i in dp]) % mod))


main()
# Original solution
def main():
    mod = 998244353
    s, k = input().split()
    k, n, one, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    mm = min(one-1, k)

    dp = [[0]*(mm+1) for _ in [0]*one]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*(mm+1) for _ in [0]*one]
        for jl in range(z+i, one):
            for x in range(i, min(one, jl+1, mm+i+1)):
                dp2[jl][x-i] = (dp2[jl][x-i]+sum([dp[jl-x+p][p]
                                                  for p in range(min(one, x-i+1))])) % mod
            for p in range(min(one, mm+1)):
                dp2[jl][p] = (dp2[jl][p]+sum([dp[jl-l][p]
                                              for l in range(min(one, i, jl-p+1))])) % mod
        z += i
        dp = dp2
    print((sum([sum(i) for i in dp]) % mod))


main()


# Optimized solution
def main():
    mod = 998244353
    s, k = input().split()
    k, n, o, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    m = min(o, k+1)

    dp = [[0]*m for _ in [0]*o]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*m for _ in [0]*o]
        dp3 = [[0] for _ in [0]*o]
        for x in range(o):
            t = 0
            for y in range(min(m, o-x)):
                t = (t+dp[x+y][y]) % mod
                dp3[x].append(t)
        dp4 = [[0]*m for _ in [0]*o]
        for y in range(m):
            t = dp[0][y]
            for x in range(1, o):
                dp4[x-1][y] = t
                t = (t+dp[x][y]) % mod
            dp4[o-1][y] = t
        for j in range(z+i, o):
            for x in range(min(j-i+1, m)):
                dp2[j][x] = (dp2[j][x]+dp3[j-x-i][min(o, x+1)]) % mod
            for p in range(m):
                dp2[j][p] = (dp2[j][p]+dp4[j][p]-dp4[max(j-i, p-1)][p]) % mod
        z += i
        dp = dp2
    print((sum([sum(i) for i in dp]) % mod))


main()
# Original solution
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#a,b,c,d = map(int,readline().split())
s,k = readline().split()


a = [len(i) for i in s.split("0")]
while a and a[-1] == 0: a.pop()

if not a:
    print((1))
    exit()

MOD = 998244353

M = sum(a)+1
k = min(int(k),M)


dp = [[0]*M for _ in range(k+1)] # j 使って（上限 k）、l 余ってる
dp[0][0] = 1

#print(a)
for ai in a[::-1]:
    ndp = [[0]*M for _ in range(k+1)] # j 使って（上限 k）、l 余ってる
    for j in range(k+1):
        for l in range(M):
            for ll in range(l):
                ndp[j][ll] += dp[j][l]
                ndp[j][ll] %= MOD
            
            V = min(M-l,k-j+1,ai+1)
            for i in range(V):
                #if j+i > k: break
                ndp[j+i][l+i] += dp[j][l]
                ndp[j+i][l+i] %= MOD
    
    dp = ndp
    #print(dp)

ans = 0
for jj in range(k+1):
    ans += dp[jj][0]

print((ans%MOD))







# Optimized solution
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#a,b,c,d = map(int,readline().split())
s,k = readline().split()


a = [len(i) for i in s.split("0")]
while a and a[-1] == 0: a.pop()

if not a:
    print((1))
    exit()

MOD = 998244353

M = sum(a)+1
k = min(int(k),M)


dp = [[0]*M for _ in range(k+1)] # j 使って（上限 k）、l 余ってる
dp[0][0] = 1

#print(a)
for ai in a[::-1]:
    ndp = [[0]*M for _ in range(k+1)] # j 使って（上限 k）、l 余ってる
    for j in range(k+1):
        for l in range(M):
            if dp[j][l]:
                for ll in range(l):
                    ndp[j][ll] += dp[j][l]
                    ndp[j][ll] %= MOD

                V = min(M-l,k-j+1,ai+1)
                for i in range(V):
                    #if j+i > k: break
                    ndp[j+i][l+i] += dp[j][l]
                    ndp[j+i][l+i] %= MOD
    
    dp = ndp
    #print(dp)

ans = 0
for jj in range(k+1):
    ans += dp[jj][0]

print((ans%MOD))
# Original solution
s,k = input().split()
K = int(k)
if s[-1] == "1":
  s += "0"
n = len(s)
ls = []
cnt = 0
for i in range(n):
  if s[i] == "0":
    ls.append(cnt)
    cnt = 0
  else:
    cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm+1)] for j in range(sm+1)] for k in range(l+1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1,l+1):
  num = ls[i-1]
  for j in range(smprv+num,sm+1):
    if j == smprv+num:
      dp[i][j][0] = 1
    for k in range(1,j+1):
      for m in range(j+1):
        if num >= m:
          dp[i][j][k] += dp[i-1][j-m][k]
        else:
          dp[i][j][k] += dp[i-1][j-m][k-(m-num)]
        dp[i][j][k] %= mod
  smprv += num
ans = 0
for i in range(sm+1):
  if i <= K:
    ans += dp[-1][-1][i]
    ans %= mod
print(ans)

# Optimized solution
s,k = input().split()
K = int(k)
if s[-1] == "1":
  s += "0"
n = len(s)
ls = []
cnt = 0
for i in range(n):
  if s[i] == "0":
    ls.append(cnt)
    cnt = 0
  else:
    cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm+1)] for j in range(sm+1)] for k in range(l+1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1,l+1):
  num = ls[i-1]
  for j in range(smprv+num,sm+1):
    if j == smprv+num:
      dp[i][j][0] = 1
    for k in range(1,j+1):
      x = 0
      for m in range(j+1):
        if num >= m:
          x += dp[i-1][j-m][k]
        else:
          x += dp[i-1][j-m][k-(m-num)]
      dp[i][j][k] = x%mod
  smprv += num
ans = 0
for i in range(sm+1):
  if i <= K:
    ans += dp[-1][-1][i]
    ans %= mod
print(ans)
# Original solution
import sys

a, b, c, d = list(map(int, sys.stdin.readline().split()))

def main():
    return 'Yes' if abs(c - a) <= d or abs(b - a) <= d and abs(c - b) <= d else 'No'

if __name__ == '__main__':
    ans = main()
    print(ans)

# Optimized solution
import sys

a, b, c, d = list(map(int, sys.stdin.readline().split()))

def main():
    ans = 'No'
    if abs(c - a) <= d: ans = 'Yes'
    elif abs(b - a) <= d and abs(c - b) <= d: ans = 'Yes'
    print(ans)

if __name__ ==  '__main__':
    main()
# Original solution
a,b,c,d = list(map(int,input().split()))
if abs(a-c) <= d or (abs(a-b) <= d and abs(c-b) <= d):
    print("Yes")
else:
    print("No")

# Optimized solution
A,B,C,D = list(map(int,input().split()))
print(("Yes" if abs(A-C)<=D or abs(A-B)<=D and abs(B-C)<=D else "No"))
# Original solution
a,b,c,d=list(map(int, input().split()))
if (abs(a-c)<=d) or (abs(a-b)<=d) and (abs(b-c)<=d):
  print('Yes')
else:
  print('No')

# Optimized solution
a,b,c,d=list(map(int, input().split()))
print(("Yes" if (abs(a-c)<=d) or (abs(a-b)<=d) and (abs(b-c)<=d) else "No"))
# Original solution
a,b,c,d = list(map(int, input().split()))
if (a-c)**2<=d**2 or ((a-b)**2<=d**2 and (b-c)**2<=d**2):
    print("Yes")
else:
    print("No")


# Optimized solution
a,b,c,d=list(map(int, input().split()))
print(("Yes" if abs(a-c)<=d or (abs(a-b)<=d and abs(b-c)<=d) else "No"))
# Original solution
a, b, c, d = list(map(int, input().split()))
if abs(b - a) <= d and abs(c - b) <= d:
    print("Yes")
elif abs(c - a) <= d:
    print("Yes")
else:
    print("No")


# Optimized solution
a, b, c, d = list(map(int, input().split()))
if abs(a-b) <= d and abs(b-c) <= d:
    print("Yes")
elif abs(a-c) <= d:
    print("Yes")
else:
    print("No")
# Original solution
a, b, c, d = list(map(int, input().split()))
print(('Yes' if abs(c - a) <= d or abs(b - a) <= d and abs(c - b) <= d else 'No'))

# Optimized solution
a, b, c, d = list(map(int, input().split()))
if abs(c - a) <= d or abs(b - a) <= d and abs(c - b) <= d:
	print('Yes')
else:
	print('No')
# Original solution
a,b,c,d=list(map(int,input().split()))
print(("Yes" if abs(c-a)<=d or (abs(b-a)<=d and abs(c-b)<=d) else "No"))

# Optimized solution
a,b,c,d=list(map(int,input().split()))
print(("Yes" if abs(c-a)<=d or abs(b-a)<=d and abs(c-b)<=d else "No"))
# Original solution
a, b, c, d = list(map(int,input().split()))

# aとcの距離の絶対値ACを定義
if (a - c) >= 0:
    AC = (a-c)
else:
    AC = (c-a)

# BがAとCの間に入る場合のみ、AB間、BC間を定義
if a < b < c:
    AB = (b - a)
    BC = (c - b)
if c < b < a:
    AB = (a-b)
    BC = (b-c)

# AとCの距離がd以下ならYes！
if AC <= d:
    print('Yes')
# AB間、BC間ともにd以下ならYes！
elif AB <= d and BC <= d:
    print('Yes')
else:
    print('No')


# Optimized solution
a, b, c, d = list(map(int,input().split()))

# aとcの距離ACを定義
if (a - c) >= 0:
    AC = (a-c)
else:
    AC = (c-a)

# BがAとCの間に入る場合のみ、AB間、BC間を定義
if a < b < c:
    AB = (b - a)
    BC = (c - b)
if c < b < a:
    AB = (a-b)
    BC = (b-c)

# AとCの距離がd以下ならYes！
if AC <= d:
    print('Yes')
# AB間、BC間ともにd以下ならYes！
elif AB <= d and BC <= d:
    print('Yes')
else:
    print('No')
# Original solution
a, b, c, d = list(map(int, input().split()))
print(("Yes" if abs(a-c) <= d or (abs(a-b) <= d and abs(b-c) <= d) else "No"))

# Optimized solution
a, b, c, d = list(map(int, input().split()))
if abs(a-c)<=d:
    print('Yes')
elif not ((a<=b<=c)or(c<=b<=a)):
    print('No')
else:
    if (abs(a-b)<=d)and(abs(b-c)<=d):
        print('Yes')
    else:
        print('No')
# Original solution
a,b,c,d = list(map(int,input().split()))

if (abs(b-a)<=d and abs(c-b)<=d) or abs(c-a)<=d:
  print("Yes")
else:
  print("No")

# Optimized solution
a,b,c,d = list(map(int,input().split()))
print(("YNeos"[(abs(a-b)>d or abs(b-c)>d) and abs(a-c)>d::2]))
# Original solution
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(eval(input()))
    l=list(map(int,input().split()))
    heikin=sum(l)/n
    samunenum=100
    samune=10**18
    for i in range(n):
        x=abs(heikin-l[i])
        if x<samune:
            samunenum=i
            samune=x
    print(samunenum)
resolve()

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(eval(input()))
    l=list(map(int,input().split()))
    samunenum=100
    samune=10**18
    for i in range(n):
        x=abs(sum(l)-n*l[i])
        if x<samune:
            samunenum=i
            samune=x
    print(samunenum)
resolve()
# Original solution
def main():
    N = int(eval(input()))
    A = [int(i) for i in input().split()]
    avg = sum(A)/N
    ans = 0
    mi = abs(A[0] - avg)
    for i, a in enumerate(A[1:], start=1):
        if abs(a - avg) < mi:
            ans = i
            mi = abs(a - avg)
    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N = int(eval(input()))
    A = [int(i) for i in input().split()]
    avg = sum(A)/N
    mi = abs(A[0] - avg)
    idx = 0
    for i, a in enumerate(A[1:], start=1):
        if abs(a - avg) < mi:
            mi = abs(a - avg)
            idx = i
    print(idx)


if __name__ == '__main__':
    main()
# Original solution
def main():
    n = int(eval(input()))
    a_list = list(map(int, input().split()))
    mean_a = sum(a_list) / n
    diff_list = [abs(a - mean_a) for a in a_list]
    min_a = min(diff_list)
    print((diff_list.index(min_a)))


if __name__ == "__main__":
    main()


# Optimized solution
def main():
    n = int(eval(input()))
    a_list = list(map(int, input().split()))
    sum_a = sum(a_list)
    min_val = 100
    min_index = 0

    for i, a in enumerate(a_list):
        d = abs(n * a - sum_a)
        if d < min_val:
            min_val = d
            min_index = i

    print(min_index)


if __name__ == "__main__":
    main()
# Original solution
n=int(eval(input()))
*a,=list(map(int,input().split()))
avg=sum(a)/n

c=[(abs(j-avg),i) for i,j in enumerate(a)]
c.sort(key=lambda x:(x[0],x[1]))
print((c[0][1]))

# Optimized solution
n=int(eval(input()))
*a,=list(map(int,input().split()))
avg=sum(a)/n

ans,m=0,1e22
for i,j in enumerate(a):
  if abs(j-avg)<m:
    ans=i
    m=abs(j-avg)

print(ans)
# Original solution
n = int(eval(input()))
w = list(map(int,input().split()))
# s1とs2の差の絶対値の最小値が最小になる部分を中心として考えれば良い
# wの最大値と最小値を順々に足したものを比較すれば良い
s1 = []
s2 = []

while len(w)>0:
  if sum(s1) <= sum(s2):
    s1.append(w.pop(0))
  else:
    s2.append(w.pop(-1))
print((abs(sum(s1)-sum(s2))))

    

# Optimized solution
n = int(eval(input()))
w = list(map(int, input().split()))
z = []
for i in range(n):
    x = sum(w[:i])
    y = sum(w[i:])
    z.append(abs(x-y))
print((min(z)))
# Original solution
l = int(eval(input()))
ws = list(map(int, input().split()))
c = 9999
for i in range(l):
    c = min([c, abs(sum(ws[i:])- sum(ws[:i]))])
print(c)


# Optimized solution
l = int(eval(input()))
ws = list(map(int, input().split()))
print((min([abs(sum(ws[i:]) - sum(ws[:i])) for i in range(l)])))
# Original solution
n = int(eval(input()))
w = list(map(int, input().split()))
a = 10**19
for i in range(1, n-1):
    a = min(abs(sum(w[:i+1]) - sum(w[i+1:])), a)
print(a)


# Optimized solution
# 問題が少しわかりずらい。
n = int(eval(input()))
w = list(map(int, input().split()))
a = 10**19
for i in range(1, n-1):
  	# 重りを二つに分け、差異の最小値を判定する。
    a = min(abs(sum(w[:i+1]) - sum(w[i+1:])), a)
print(a)
# Original solution
n = int(eval(input()))
l = list(map(int, input().split()))

print((min(abs(sum(l[:i])-sum(l[i:])) for i in range(1,n))))

# Optimized solution
eval(input())
l=list(map(int,input().split()))
s=sum(l)
a,t=s,0
for i in l: t+=i; a=min(a,abs(s-t*2))
print(a)
# Original solution
# B - Balance

n = int(eval(input()))
w = list(int(x) for x in input().split())

ans = 10**6
for i in range(1, n):
    ans = min(ans, abs(sum(w[:i]) - sum(w[i:])))

print(ans)

# Optimized solution
# B - Balance

n = int(eval(input()))
w = list(int(x) for x in input().split())

wsum = [0]
for i in range(n):
    wsum.append(wsum[i] + w[i])

ans = 10**6
for i in range(1, n):
    ans = min(ans, abs(wsum[n]-wsum[i]-wsum[i]))

print(ans)
# Original solution
N = int(eval(input()))
W = list(map(int, input().split()))
l = []
for T in range(N):
    sum1 = sum(W[:T+1])
    sum2 = sum(W[T+1:])
    d = abs(sum1-sum2)
    l.append(d)
print((min(l)))

# Optimized solution
N = int(eval(input()))
W = list(map(int, input().split()))
l = []
for T in range(N):
    sum1 = sum(W[:T])
    sum2 = sum(W[T:])
    d = abs(sum1-sum2)
    l.append(d)
print((min(l)))
# Original solution
N = int(eval(input()))
W = list(map(int, input().split()))
ww = []
for i in range(N):
  ww.append(sum(W[0:i+1]))
ans = [abs((2 * q) - ww[N-1]) for q in ww]
print((min(ans)))

# Optimized solution
N = int(eval(input()))
W = list(map(int, input().split()))
ans = [abs(sum(W[0:i+1]) - sum(W[i+1:])) for i in range(N-1)]
print((min(ans)))
# Original solution
# 129 B

n = int(eval(input()))
l = list(map(int, input().split()))
diff = (100 ** 100)

for t in range(len(l)):
    s1 = 0
    s2 = 0

    for i in range(len(l)):
        if i <= t:
            s1 += l[i]
        else:
            s2 += l[i]
    x = abs(s2 - s1)     
    if x <= diff:
        diff = x 
         
print(diff)
    


# Optimized solution
n = int(eval(input()))
w = list(map(int, input().split()))
p = [0 for i in range(n)]
p[0] = w[0]
for i in range(1, n):
    p[i] = p[i-1] + w[i]
diff = float('inf')
for j in range(n):
    cd = abs(p[n-1] - (2*p[j]))
    diff = min(diff, cd)
print(diff)
# Original solution
n = int(eval(input()))
w = list(map(int, input().split()))
ans = 10000000000
for t in range(1, n):
    left, right = 0, 0
    for i in range(t):
        left += w[i]
    for i in range(t, n):
        right += w[i]
    ans = min(ans, abs(left - right))
print(ans)


# Optimized solution
n = int(eval(input()))
w = list(map(int, input().split()))
ans = 10000000000
for t in range(1, n):
    left = sum(w[:t])
    right = sum(w[t:])
    ans = min(ans, abs(left - right))
print(ans)
# Original solution
N = int(eval(input()))
W = list(map(int, input().split()))
 
# O(N^2)で解いても間に合う
m = 10**10
for i in range(1, N):
  a, b = 0, 0
  for j in range(i):
    a += W[j]
  for j in range(i, N):
    b += W[j]
  m = min(m, abs(a-b))
print(m)

# Optimized solution
N = int(eval(input()))
W = list(map(int, input().split()))

# 累積和 => O(N)
S = [0] * N
S[0] = W[0]
for i in range(N-1):
  S[i+1] = S[i] + W[i+1]
  
# S[0] = W[0]
# S[1] = W[0] + W[1]
# S[2] = W[0] + W[1] + W[2]
# S[N-1] = W[0] + W[1] + ... + W[N-1]

# S[i] = W[0] + ... + W[i]
# S[N-1] - S[i] = W[i+1] + ... + W[N-1]

m = 10**10
for i in range(N-1):
  m = min(m, abs(S[N-1] - 2*S[i]))

print(m)
# Original solution
n = int(eval(input()))
w = list(map(int, input().split()))

ans = 10 ** 9
for t in range(n):
    cnt = 0
    for i in range(n):
        a = 1
        if i > t:
            a = -1
        cnt += a * w[i]
    ans = min(ans, abs(cnt))
    
print(ans)

# Optimized solution
n = int(eval(input()))
w = list(map(int, input().split()))

ans = 10 ** 9
now = sum(w)

for i in range(n):
    now -= 2 * w[i]
    ans = min(ans, abs(now))

print(ans)
# Original solution

n = int(eval(input()))
lst = list(map(int,input().split()))
lst2 = [0]*n
all_sum = 0
for e in lst:
    all_sum += e

for i in range(n):
    for j in range(i+1):
        lst2[i] += lst[j]


for before,now in zip(lst2,lst2[1:]):
    if abs(abs(now-all_sum)-abs(now))<abs(abs(before-all_sum)-abs(before)):
        ans = abs(abs(now-all_sum)-abs(now))
    else:break

print(ans)




# Optimized solution

n = int(eval(input()))
lst = list(map(int,input().split()))

ans = None
for t in range(n-1):
    left = [x for x in lst[:t+1]]#t+1未満まで
    right = [x for x in lst[t+1:]]#t＋1以上

    sum_left=0
    for e in left:
        sum_left+=e

    sum_right=0
    for e in right:
        sum_right+=e

    if ans==None or abs(sum_left-sum_right)<ans:
        ans = abs(sum_left-sum_right)
    else:break
print(ans)
# Original solution
n = int(eval(input()))
w = list(map(int, input().split()))
l =[]
for i in range(n):
    l.append(abs(sum(w[:i]) - sum(w[i:])))
print((min(l)))

# Optimized solution
n = int(eval(input()))
w = list(map(int, input().split()))
ans = 10000
for i in range(n):
    s = abs(sum(w[:i]) - sum(w[i:]))
    ans = min(s,ans)
print(ans)
# Original solution
import sys

stdin = sys.stdin

mod = 1000000007
inf = 1 << 60

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n = ni()
w = na()

ans = inf
d = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(1, n + 1):
	d[i] = w[i - 1] + d[i - 1]
	b[i] = w[n - i] + b[i - 1]
b.reverse()
for i in range(1, n):
	ans = min(ans, abs(d[i] - b[i]))

print(ans)


# Optimized solution
import sys

stdin = sys.stdin

mod = 1000000007
inf = 1 << 60

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n = ni()
w = na()

ans = inf
s = sum(w)
p = 0
for i in range(n):
	p += w[i]
	ans = min(ans, abs(s - p - p))

print(ans)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
mini=float('inf')
sum1=0
sum2=sum(a)
t=0
while t<10**7:
	t+=1
for i in range(n):
    sum1=sum1+a[i]
    sum2=sum2-a[i]
    mini=min(mini,abs(sum1-sum2))
print(mini)

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
mini=float('inf')
sum1=0
sum2=sum(a)
t=0
while t<n:
    sum1=sum1+a[t]
    sum2=sum2-a[t]
    mini=min(mini,abs(sum1-sum2))
    t+=1
print(mini)
# Original solution
n = int(eval(input()))
arr = list(map(int, input().split()))

dic = {}
for i in range(1,n+1):  
  S1 = sum(arr[:i])  
  S2 = sum(arr[i:])  
  dic[i] = abs(S1-S2)  
ans = sorted(list(dic.items()), key=lambda x:x[1])  

print((ans[0][1]))  
  

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

ans = 1<<60
for t in range(1, N):
  L = sum(A[:t])  
  R = sum(A[t:])
  ans = min(ans, abs(L-R))
  
print(ans)
# Original solution
x = 10**9
n = int(eval(input()))
w = list(map(int,input().split()))
for i in range(n):
    g,t = 0,0
    for j in range(i):
        g+=w[j]
    for k in range(n-i):
        t+=w[n-k-1]
    x = min(x,abs(g-t))
print(x)

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
s,g = sum(a),0
ans = s
for i in a:
    g+=i
    s-=i
    ans = min(ans,abs(s-g))
print(ans)
# Original solution
n = int(eval(input()))
lst_W = list(map(int, input().split()))
ans = 999
for t in range(n):
	low = sum(lst_W[:t])
	high = sum(lst_W[t:])
	if ans > abs(high - low):
		ans = abs(high - low)
print(ans)

# Optimized solution
n = int(eval(input()))
w_lst = list(map(int, input().split()))
min = 1000000
for i in range(1, n):
    s1 = sum(w_lst[:i])
    s2 = sum(w_lst[i:])
    if abs(s1 - s2) < min:
        min = abs(s1 - s2)
print(min)