CodeEff/ECCO huggingface dataset:
# Original solution
def sub(i,li):
    j = i + 1
    sub_max = 0
    for k in range(len(li) - j):
        if sub_max < abs(li[j] - li[i]):
            sub_max = abs(li[j] - li[i])
        j += 1
    return sub_max

n = int(eval(input()))
li = list(map(int,input().split()))
max_num = 0
for i in range(len(li)):
    a = sub(i,li)
    if a > max_num:
        max_num = a
print(max_num)

# Optimized solution
n = int(eval(input()))
li = list(map(int,input().split()))
M = 0
for i in range(n):
        for j in range(i,n):
                a = abs(li[i] - li[j])
                if a > M:
                        M = a
print(M)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
ans = 0
for i in range(N):
	for j in range(i, N):
		ans = max(ans, abs(A[i] - A[j]))
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
print((max(A) - min(A)))
# Original solution
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools

# 標準入力を取得
N = int(eval(input()))
A = list(map(int, input().split()))

# 求解処理
ans = 0
for A_i, A_j in itertools.combinations(A, r=2):
    ans = max(ans, abs(A_i - A_j))

# 結果出力
print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(eval(input()))
    A = list(map(int, input().split()))

    return N, A


def main(A: list) -> None:
    """
    メイン処理.

    Args:\n
        A (list): 整数列(1 <= A_i <= 10^9)
    """
    # 求解処理
    ans = max(A) - min(A)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A = get_input()

    # メイン処理
    main(A)
# Original solution
# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(eval(input()))
    A = list(map(int, input().split()))

    return N, A


def main(A: list) -> None:
    """
    メイン処理.

    Args:\n
        A (list): 整数列(1 <= A_i <= 10^9)
    """
    # 求解処理
    ans = max(A) - min(A)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A = get_input()

    # メイン処理
    main(A)


# Optimized solution
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(eval(input()))
    A = list(map(int, input().split()))

    return N, A


def main(A: list) -> None:
    """
    メイン処理.

    Args:\n
        A (list): 整数列(1 <= A_i <= 10^9)
    """
    # 求解処理
    ans = 0
    for A_i, A_j in itertools.combinations(A, r=2):
        ans = max(ans, abs(A_i - A_j))

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A = get_input()

    # メイン処理
    main(A)
# Original solution
import itertools
N = int(eval(input()))

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

res = max([abs(x - y) for x, y in itertools.combinations(An, 2)])

print(res)

# Optimized solution
N = int(eval(input()))

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

# res = max([abs(x - y) for x, y in itertools.combinations(An, 2)])
mn = An[0]
mx = An[0]
for i in An:
    if mn > i:
        mn = i
    if mx < i:
        mx = i

print((mx - mn))
# Original solution
N = int(eval(input()))
*A, = list(map(int, input().split()))

max = 0

for i in range(N):
    for j in range(i+1,N):
        temp = abs(A[i]-A[j])
        if max < temp:
            max = temp
print(max)

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

A.sort()
print((abs(A[0]-A[N-1])))
# Original solution
N = int(eval(input()))
As = [int(i) for i in input().split()]

m = -1
for i in range(N-1):
    for j in range(i+1, N):
        m = max(abs(As[i] - As[j]), m)
print(m)


# Optimized solution
N = int(eval(input()))
As = [int(i) for i in input().split()]

# m = -1
# for i in range(N-1):
#     for j in range(i+1, N):
#         m = max(abs(As[i] - As[j]), m)
# print(m)

print((max(As) - min(As)))
# Original solution
N = int(eval(input()))
L = list(map(int, input().split()))

diff = 0
maxNum = 0
maxDiffArray = []
for i in range(len(L)):
    diffArray = []
    for j in range(len(L)):
        if i != j:
            diff = abs(L[i] - L[j])
            diffArray.append(diff)
    maxDiffArray.append(max(diffArray))
print((max(maxDiffArray)))


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

# diff = 0
# maxNum = 0
# maxDiffArray = []
# for i in range(len(L)):
#     diffArray = []
#     for j in range(len(L)):
#         if i != j:
#             diff = abs(L[i] - L[j])
#             diffArray.append(diff)
#     maxDiffArray.append(max(diffArray))
# print(max(maxDiffArray))

# 別解：数列の最大値と最小値の差が要素間の差の最大値となることを利用
print((max(L) - min(L)))
# Original solution
if __name__ == '__main__':

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

	print((max(A) - min(A)))


# Optimized solution
if __name__ == '__main__':

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

	print((abs(max(A) - min(A))))
# Original solution
N = int(eval(input()))
Alist = list(map(int,input().split()))
p =[]
for i in range(N):
    for j in range(N):
        p.append(abs(Alist[i]-Alist[j]))
print((max(p)))

# Optimized solution
N = int(eval(input()))
a = list(map(int,input().split()))
p =[]
for i in range(N):
    for j in range(N):
        p.append(abs(a[i]-a[j]))
print((max(p)))
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))
dmax = 0
for i in range(n-1):
    for j in range(i+1,n):
        dmax = max(dmax, abs(A[i]-A[j]))
print(dmax)


# Optimized solution
_ = eval(input())
A = list(map(int, input().split()))
print((abs(max(A) - min(A))))
# Original solution
N = int(eval(input()))
A_list = [int(a) for a in input().split()]
list = []
for j in range(N):
    for k in range(N):
        list.append(abs(A_list[j]-A_list[k]))
print((max(list)))

# Optimized solution
N = int(eval(input()))
A_list = [int(a) for a in input().split()]
A_list.sort()
print((A_list[-1]-A_list[0]))
# Original solution
n, a = int(eval(input())), list(map(int, input().split()))
s = []
for i in range(n):
  for p in range(n):
    s.append(a[i] - a[p])
print((max(s)))

# Optimized solution
n, a = int(eval(input())), list(map(int, input().split()))
s = []
for i in range(n):
  for p in range(i):
    s.append(abs(a[i] - a[p]))
print((max(s)))
# Original solution
# -*- coding: utf-8 -*-

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

A.sort()
max_diff = A[N-1] - A[0]
print(max_diff)


# Optimized solution
# -*- coding: utf-8 -*-

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

max_A = min_A = A[0]
for i in range(1,N,1):
    if A[i] > max_A:
        max_A = A[i]
    if A[i] < min_A:
        min_A = A[i]

max_diff = max_A - min_A
print(max_diff)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
ans = 0

from itertools import combinations

for i, j in combinations(A, 2):
    ans = max(ans, abs(i - j))

print(ans)

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

A = sorted(A)
print((A[-1] - A[0]))
# Original solution
total_integer = int(eval(input()))
integer = sorted(list(map(int, input().split())))
print((integer[total_integer - 1] - integer[0]))

# Optimized solution
eval(input())
A = list(map(int, input().split()))
print((max(A) - min(A)))
# Original solution
eval(input())
a=sorted(map(int,input().split()))
print((a[-1]-a[0]))

# Optimized solution
eval(input())
A = sorted(map(int, input().split()))
print((A[-1]-A[0]))
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
s = []
for i in range(n):
    for j in range(n):
        s.append(a[i]-a[j])
print((max(s)))

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
print((max(a)-min(a)))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
res = a[-1] - a[0]
print(res)


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

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        ans = max(ans, abs(a[i] - a[j]))

print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
max = 0
for a1 in a:
    for a2 in a:
        if max < abs(a1 - a2):
            max = abs(a1 - a2)

print(max)


# Optimized solution
n=int(eval(input()))
a=list(map(int, input().split()))
a.sort()
print((a[-1]-a[0]))
# Original solution
def actual(N, a_list):
    s = set(a_list)
    num_max = max(s)
    num_min = min(s)

    return abs(num_max - num_min)


N = int(eval(input()))
a_list = list(map(int, input().split()))

print((actual(N, a_list)))

# Optimized solution
def actual(N, a_list):
    s = set(a_list)
    
    return max(s) - min(s)


N = int(eval(input()))
a_list = list(map(int, input().split()))

print((actual(N, a_list)))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
ma = 0
for i in range(n):
    for j in range(i + 1, n):
        ma = max(ma, abs(a[i] - a[j]))
print(ma)


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
print((abs(a[0] - a[-1])))
# Original solution
n = eval(input())
a = list(map(int,input().split()))
print((abs(max(a)-min(a))))

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
A.sort()
print((abs(A[-1]-A[0])))
# Original solution
N = int(eval(input()))
A = [int(i) for i in input().split()]

ans = 0
for j in range(len(A) - 1):
  for k in range(j + 1, len(A)):
    ans = max(ans, abs(A[j] - A[k]))
print(ans)

# Optimized solution
N = int(eval(input()))
A = [int(i) for i in input().split()]

ans = max(A) - min(A)
print(ans)
# Original solution
a,b,*c=list(map(int,input().split()));print(('Balanced'if a+b==sum(c) else'RLiegfhtt'[a+b>sum(c)::2]))

# Optimized solution
a,b,c,d=list(map(int,input().split()));print(('Balanced'if a+b==c+d else'RLiegfhtt'[a+b>c+d::2]))
# Original solution
A, B, C, D = list(map( int, input().split()))
L = A + B
R = C
print((["Balanced","Left","Right"][((C+D)<(A + B)) - ((C+D)>(A + B))]))

# Optimized solution
A,B,C,D=list(map(int,input().split()))
print((["Balanced","Left","Right"][(C+D<A+B)-(C+D>A+B)]))
# Original solution
a,b,c,d = list(map(int, input().split()))
a, c = a+b, c+d
if a == c:
  print('Balanced')
elif a > c:
  print('Left')
else:
  print('Right')

# Optimized solution
a,b,c,d = list(map(int, input().split()))
a, c = a+b, c+d
if a == c:
  print('Balanced')
else:
  print((['Right', 'Left'][a > c]))
# Original solution
a,b,c,d=list(map(int,input().split()));e=a+b;f=c+d;print((['RLiegfhtt'[e>f::2],'Balanced'][e==f]))

# Optimized solution
a,b,c,d=list(map(int,input().split()));print((['RLiegfhtt'[a+b>c+d::2],'Balanced'][a+b==c+d]))
# Original solution
A,B,C,D = list(map(int,input().split()))
print((["Balanced","Left","Right"][(A+B>C+D)-(A+B<C+D)]))

# Optimized solution
A,B,C,D = list(map(int,input().split()))
w1 = A+B
w2 = C+D

if w1<w2:
  print("Right")
elif w1==w2:
  print("Balanced")
else:
  print("Left")
# Original solution
a,b,c,d = list(map(int,input().split()))
if a+b > c+d:
    print('Left')
elif a+b == c+d:
    print('Balanced')
else:
    print('Right')

# Optimized solution
a,b,c,d = list(map(int,input().split()))
if a+b>c+d:
  print('Left')
elif a+b<c+d:
  print('Right')
else:
  print('Balanced')
# Original solution
A, B, C, D = list(map(int,input().split()))
left = A + B
right = C + D
if(left > right):
  print('Left')
elif(left < right):
  print('Right')
else:
  print('Balanced')

# Optimized solution
A, B, C, D = list(map(int,input().split()))
L = A+B
R = C+D
if(L > R):
  print("Left")
elif(L == R):
  print("Balanced")
else:
  print("Right")
# Original solution
A, B, C, D = list(map(int,input().split()))
L = A+B
R = C+D
if(L > R):
  print("Left")
elif(L == R):
  print("Balanced")
else:
  print("Right")

# Optimized solution
A, B, C, D = list(map(int,input().split()))
if(A+B > C+D):
  print("Left")
elif(A+B < C+D):
  print("Right")
else:
  print("Balanced")
# Original solution
import bisect
import sys
sys.setrecursionlimit(10000)
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(eval(input()))
if n&1:print((-1));exit()
f(a,0,n)
a=sorted(a)+[10**20]
b=g(n,0)
if b<0:b=-1
print(b)

# Optimized solution
import bisect
import sys
sys.setrecursionlimit(10000)
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(eval(input()))
if n&1:print((-1));exit()
f(a,0,n)
a=sorted(a)
b=g(n,0)
if b<0:b=-1
print(b)
# Original solution
while True:
      n, m = list(map(int, input().split()))
      if n == 0 and m == 0:
            break
      p = [ 1 for i in range(n) ]
      pn = n; count = 0; flag = 1
      while flag == 1:
            for i in range(n):
                  if p[i] == 1:
                        count += 1
                        if count == m:
                              p[i] = 0
                              count = 0
                              pn -= 1
                              if pn == 1:
                                    flag = 0
                                    break

      print(p.index(1)+1)

# Optimized solution
while True:
      n, m = list(map(int, input().split()))
      if n == 0 and m == 0:
            break
      p = [ i+1 for i in range(n) ]
      np = n; a = 0
      while np > 1:
            a = (a+m-1)%len(p)
            p.pop(a)
            np -= 1
      print(p[0])
# Original solution
while 1:
  n,m = list(map(int,input().split()))
  if n==0 & m==0: break
  G = list(range(1, n+1))
  while n>1:
    if m%n == 0: G = G[:n-1]
    else: G = G[m % n:] + G[:(m-1) % n]
    n-=1
  print(G[0])

# Optimized solution
while 1:
  n,m=list(map(int,input().split()))
  if n==0==m:break
  G=list(range(1,n+1))
  p=0
  while n>1:
    p=(p+m-1)%n
    G.pop(p)
    n-=1
  print(G[0])
# Original solution
import sys
dp=[0]*10001
for line in sys.stdin.readlines():
    n = int(line)
    dp[0]=1
    for i in range(1,n+1):
        dp[i]=dp[i-1]+i
    print(dp[n])

# Optimized solution
import sys
for line in sys.stdin.readlines():
    n = int(line)
    dp=1
    for i in range(1,n+1):
        dp+=i
    print(dp)
# Original solution
A, B = list(map(int, input().split()))

if A * B % 2 == 0:
  print("No")
else:
  print("Yes")

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

print(("Yes" if (a*b) % 2 != 0 else "No"))
# Original solution
a,b = list(map(int, input().split()))
c=0
for i in range(4):
  if a*b*i %2!=0:
    c+=1
  else:
    c=0
print(('No' if c==0 else 'Yes'))

# Optimized solution
a,b = list(map(int, input().split()))
print(('Yes' if a*b %2 !=0 else 'No'))
# Original solution
a,b=list(map(int,input().split()))
print(("Yes" if (a*b)%2 else "No"))


# Optimized solution
print((["No","Yes"][(lambda a:(a[0]*a[1])%2)(list(map(int,input().split())))]))
# Original solution
def iin(): return int(eval(input()))
def nl(): return list(map(int, input().split()))

a, b = nl()
print(('No' if a * b % 2 == 0 else 'Yes'))

# Optimized solution
a, b = list(map(int, input().split()))
print(('Yes' if a * b % 2 == 1 else 'No'))
# Original solution
A, B = list(map(int,input().split()))

count=0 #初期化
for C in range(1,4):
    if A*B*C %2 ==1:
        count=count+1#Cに順番に１、２、３と代入していく中で、A×B×C が奇数になるたんびにcountに１加算していく
if count>0: #A×B×Cが奇数になるようなCが少なくとも１つ存在していたらYesと表示したい
    print("Yes")
    
else:
    print("No")

# Optimized solution
A,B=list(map(int,(input().split())))
count=0

for C in range(1,4):
    if A*B*C%2==1:
        count=count+1

if count>=1:
    print('Yes')

elif count==0:
    print('No')
# Original solution
A, B = list(map(int,input().split()))
if(A%2 == B%2 == 1):
  print("Yes")
else:
  print("No")

# Optimized solution
A, B = list(map(int,input().split()))
if((A*B)%2 == 1):
  print("Yes")
else:
  print("No")
# Original solution
A, B = list(map(int,input().split()))
if((A*B)%2 == 1):
  print("Yes")
else:
  print("No")

# Optimized solution
def ans():
  a, b = list(map(int,input().split()))
  if((a*b)%2 == 0):
    print("No")
  else:
    print("Yes")
ans()
# Original solution
a, b = list(map(int, input().split()))
if (a * b) % 2 == 0:
    print('No')
else:
    print('Yes')

# Optimized solution
A, B = list(map(int, input().split()))
if A * B % 2 == 0:
    print('No')
else:
    print('Yes')
# Original solution
n, k = list(map(int, input().split()))

plst = []
xlst = []
ylst = []
dlst = []

for i in range(n):
  x1,y1,d1,x2,y2,d2 = list(map(int, input().split()))
  plst.append((x1,y1,d1,x2,y2,d2))
  xlst.append(x1)
  xlst.append(x2)
  ylst.append(y1)
  ylst.append(y2)
  dlst.append(d1)
  dlst.append(d2)

xlst = list(set(xlst))
ylst = list(set(ylst))
dlst = list(set(dlst))

xlst.sort()
ylst.sort()
dlst.sort()

xdic = {}
ydic = {}
ddic = {}

for i, v in enumerate(xlst):
  xdic[v] = i
for i, v in enumerate(ylst):
  ydic[v] = i
for i, v in enumerate(dlst):
  ddic[v] = i

new_map = [[[0] * len(dlst) for _ in ylst] for _ in xlst]

for p in plst:
  x1, y1, d1, x2, y2, d2 = p
  x1, y1, d1, x2, y2, d2 = xdic[x1], ydic[y1], ddic[d1], xdic[x2], ydic[y2], ddic[d2]
  for x in range(x1, x2):
    for y in range(y1, y2):
      for d in range(d1, d2):
        new_map[x][y][d] += 1

ans = 0
for i in range(len(xlst) - 1):
  for j in range(len(ylst) - 1):
    for z in range(len(dlst) - 1):
      x, y, d = xdic[xlst[i]], ydic[ylst[j]], ddic[dlst[z]]
      if new_map[x][y][d] >= k:
        ans += (xlst[i + 1] - xlst[i]) *(ylst[j + 1] - ylst[j]) * (dlst[z + 1] - dlst[z])
print(ans)


# Optimized solution
def main():
  n, k = list(map(int, input().split()))
  
  plst = []
  xlst = []
  ylst = []
  dlst = []
  
  for i in range(n):
    x1,y1,d1,x2,y2,d2 = list(map(int, input().split()))
    plst.append((x1,y1,d1,x2,y2,d2))
    xlst.append(x1)
    xlst.append(x2)
    ylst.append(y1)
    ylst.append(y2)
    dlst.append(d1)
    dlst.append(d2)
  
  xlst = list(set(xlst))
  ylst = list(set(ylst))
  dlst = list(set(dlst))
  
  xlst.sort()
  ylst.sort()
  dlst.sort()
  
  xdic = {}
  ydic = {}
  ddic = {}
  
  for i, v in enumerate(xlst):
    xdic[v] = i
  for i, v in enumerate(ylst):
    ydic[v] = i
  for i, v in enumerate(dlst):
    ddic[v] = i
  
  new_map = [[[0] * len(dlst) for _ in ylst] for _ in xlst]
  
  for p in plst:
    x1, y1, d1, x2, y2, d2 = p
    x1, y1, d1, x2, y2, d2 = xdic[x1], ydic[y1], ddic[d1], xdic[x2], ydic[y2], ddic[d2]
    for x in range(x1, x2):
      for y in range(y1, y2):
        for d in range(d1, d2):
          new_map[x][y][d] += 1
  
  ans = 0
  for i in range(len(xlst) - 1):
    xlsti = xlst[i]
    xlsti1 = xlst[i + 1]
    x = xdic[xlsti]
    for j in range(len(ylst) - 1):
      ylstj = ylst[j]
      ylstj1 = ylst[j + 1]
      y = ydic[ylstj]
      for z in range(len(dlst) - 1):
        dlstz = dlst[z]
        dlstz1 = dlst[z + 1]
        d = ddic[dlstz]
        if new_map[x][y][d] >= k:
          ans += (xlsti1 - xlsti) * (ylstj1 - ylstj) * (dlstz1 - dlstz)
  print(ans)

main()
# Original solution
# -*- coding: utf-8 -*-
from decimal import Decimal
from itertools import permutations

# 整数の入力
N = int(eval(input()))

# スペース区切りの整数の入力
V = list(map(Decimal, input().split()))

result = 0

for values in permutations(V, N):
    new_result = values[0]

    for value in values[1:]:
        new_result = (new_result + value) / 2

    if result < new_result:
        result = new_result

# 出力
print(result)


# Optimized solution
# -*- coding: utf-8 -*-
from decimal import Decimal
from itertools import permutations

# 整数の入力
N = int(eval(input()))

# スペース区切りの整数の入力
V = list(map(Decimal, input().split()))

result = 0

V = sorted(V)
result = V[0]

for value in V[1:]:
    result = (result + value) / 2


# 出力
print(result)
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s-1)//2)
while True:
  t = b&(-b)
  #print(i,t,b)
  if (s+1)//2 <= t.bit_length()-1 <= s:
    print((t.bit_length()-1))
    break
  b ^= t

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s-1)//2)
while True:
  t = b&(-b)
  T = t.bit_length()-1
  if (s+1)//2 <= T <= s:
    print(T)
    break
  b ^= t
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1)
    for c in a:
        t |= t << c
    t %= m

    return s - (t.bit_length() - 1)


print(main())




# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1) - 1
    for c in a:
        t |= t << c
    t &= m

    return s - (t.bit_length() - 1)


print(main())
# Original solution
_,a=open(0)
*a,=list(map(int,a.split()))
d=1
for i in a:d|=d<<i
s=0--sum(a)//2
print((bin(d)[~s::-1].find('1')+s))

# Optimized solution
def main():
  _,a=open(0)
  *a,=list(map(int,a.split()))
  d=1
  for i in a:d|=d<<i
  s=0--sum(a)//2
  d>>=s
  print(((d&-d).bit_length()+s-1))
main()
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

sumA = sum(A)
ct = {0:1}

for a in A:
  nct = {}
  for k in ct:
    nct[k] = nct.get(k, 0) + ct[k]
    nct[k+a] = nct.get(k+a, 0) + ct[k]
  ct = nct

ct[0] = 0
medidx = (2**N)//2
n = 0
keys = list(ct.keys())
keys.sort()
for key in keys:
  n += ct[key]
  if n >= medidx:
    print(key)
    exit()

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

sumA = sum(A)
halfA = math.ceil(sumA / 2)
bitset = 1
for a in A:
  bitset |= bitset << a

bitset >>= halfA
i = 0
while i < halfA:
  if bitset & 1:
    print((i+halfA))
    exit()
  bitset >>= 1
  i += 1
print((i+halfA))
# Original solution
N = int(eval(input()))
A = [int(a) for a in input().split()]
s = 1
for a in A:
    s |= s << a

for i in range((sum(A)+1)//2, sum(A)+1):
    if s & (1<<i):
        print(i)
        break

# Optimized solution
N = int(eval(input()))
A = [int(a) for a in input().split()]
s = 1
for a in A:
    s |= s << a

ss = bin(s)
for i in range((sum(A)+1)//2, sum(A)+1):
    if ss[-i-1] == "1":
        print(i)
        break