Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
import math
# import numpy
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N,M = map(int, sys.stdin.readline().split())
list_A = list(map(int, sys.stdin.readline().split()))
list_A.sort(reverse=True)

for i in range(M):
    # list_A.sort(reverse=True)
    idx_max = list_A.index(max(list_A))
    list_A[idx_max] = int(list_A[idx_max]/2) 

ans = 0

for i in range(N):
    ans += list_A[i]

print(ans)


### FIXED CODE ###

import sys
import math
import numpy as np
from fractions import gcd

import heapq

# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N,M = map(int, sys.stdin.readline().split())
list_A = list(map(int, sys.stdin.readline().split()))
# list_A.sort(reverse=True)

# list_A_np = np.array(list_A)

# hq = heapq.heapify(list_A)
for i in range(N):
    list_A[i] = -list_A[i]

heapq.heapify(list_A)
# print(list_A)
# print(int(-4.34))

for i in range(M):
    tmp = heapq.heappop(list_A)
    heapq.heappush(list_A, int(tmp/2))

# for i in range(M):
    # list_A.sort(reverse=True)
    # idx_max = list_A.index(max(list_A))
    # list_A[idx_max] = int(list_A[idx_max]/2)

    # if(list_A[0] > list_A[1]):
    #     list_A[0] = int(list_A[0]/2)
    # else:
    #     list_A.sort(reverse=True)
    #     list_A[0] = int(list_A[0]/2)


    # if(list_A_np[0] > list_A_np[1]):
    #     list_A_np[0] = int(list_A_np[0]/2)
    # else:
    #     # idx_max = list_A_np.argmax()
    #     # list_A_np[idx_max] = int(list_A_np[idx_max]/2)
    #     list_A_np = np.sort(list_A_np)[::-1]
    #     list_A_np[0] = int(list_A_np[0]/2)

    # idx_max = list_A_np.argmax()
    # list_A_np[idx_max] = int(list_A_np[idx_max]/2)

ans = 0

for i in range(N):
    # ans += list_A[i]
    # ans += list_A_np[i]
    # ans += hq.pop
    ans += heapq.heappop(list_A)

print(-ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k=int(input())
sum = 0

for a in range(k+1):
    for b in range(k+1):
        for c in range(k+1):
            if a != 0 and b != 0 and c != 0:
                sum = sum + gcd(a,b,c)

print(sum)

### FIXED CODE ###

import math
from functools import reduce

k=int(input())
sum = 0

for a in range(k+1):
    for b in range(k+1):
        tmp = math.gcd(a,b)
        for c in range(k+1):
            if a != 0 and b != 0 and c != 0:
                sum = sum + math.gcd(tmp,c)

print(sum)
### BUGGY CODE ###

N = int(input())
M = [[0 for col in range(N)] for row in range(N)]

for i in range(N-1):
    a, b, c = list(map(int, input().split(" ")))
    M[a-1][b-1] = M[b-1][a-1] = c

Qn, K = list(map(int, input().split(" ")))

Q = []
for i in range(Qn):
    Q.append(list(map(int, input().split(" "))))

def dfs(k, graph, dist):
    result = {}
    for n in range(N):
        x = graph[k][n]
        if x != 0:
            result[n] = dist + x
            graph[n][k] = 0
            result.update(dfs(n, graph, dist + x))
    return result

result = dfs(K-1, M, 0)

for q in Q:
    print(result[q[0]-1] + result[q[1]-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input())
M = [[] for i in range(N+1)]

for i in range(N-1):
    a, b, c = list(map(int, input().split(" ")))
    M[a].append((b,c))
    M[b].append((a,c))

Qn, K = list(map(int, input().split(" ")))

Q = []
for i in range(Qn):
    Q.append(list(map(int, input().split(" "))))

distance = [0]*(N+1)

def dfs(k, parent, dist):
    for n, x in M[k]:
        if n != parent:
            distance[n] = dist + x
            dfs(n, k, dist + x)

dfs(K, 0, 0)
for q in Q:
    print(distance[q[0]] + distance[q[1]])
### BUGGY CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
#print(a)
for i in range(n-2):
    for j in range(i+1, n-1):
        l = bisect_right(a, max(abs(a[i] - a[j]), a[j]))
        r = bisect_left(a, abs(a[i] + a[j]))
        #print(a[i], a[j], l, r)
        ans = ans - l + r
print(ans)

### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans = ans - j - 1 + bisect_left(a, abs(a[i] + a[j]))
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())

room = [[True if c == "." else False for c in input()] for _ in range(H)]

count = []

for i in range(H):
    count.append([0] * W)


def check(row,col):
    px = col
    py = row
    while py >= 0:
        if not room[py][px]:
            break
        count[py][px] += 1
        py -= 1
    py = row + 1
    while py < H:
        if not room[py][px]:
            break
        count[py][px] += 1
        py += 1
    py = row

    while px >= 0:
        if not room[py][px]:
            break
        count[py][px] += 1
        px -= 1
    px = col + 1
    while px < W:
        if not room[py][px]:
            break
        count[py][px] += 1
        px += 1


for row in range(H):
    for col in range(W):
        if room[row][col]:
            check(row, col)

ans = 0

for rowline in count:
    ans = max(max(rowline), ans)

print((ans - 1))

### FIXED CODE ###

H, W = map(int, input().split())

room = [[True if c == "." else False for c in input()] for _ in range(H)]

count = []

for i in range(H):
    count.append([0] * W)

for row in range(H):
    start = 0
    for col in range(W):
        if not room[row][col]:
            if col != 0:
                plus = col - start
                for i in range(start, col):
                    count[row][i] += plus
            start = col + 1
    if room[row][W - 1]:
        plus = W - start
        for i in range(start, W):
            count [row][i] += plus

for col in range(W):
    start = 0
    for row in range(H):
        if not room[row][col]:
            if row != 0:
                plus = row - start
                for i in range(start, row):
                    count[i][col] += plus
            start = row + 1
    if room[H - 1][col]:
        plus = H - start
        for i in range(start, H):
            count[i][col] += plus

ans = 0

for rowline in count:
    ans = max(max(rowline), ans)

print((ans - 1))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

_input = sys.stdin.readlines()
array_length = int(_input[0])
array = list(map(int, _input[1].split()))
# print(array_length, array)
# assert array_length == len(array)


def merge(A, left, mid, right):
    global count

    n1 = mid - left
    n2 = right - mid
    L = [0 for _ in range(n1 + 1)]
    R = [0 for _ in range(n2 + 1)]

    for m in range(n1):
        L[m] = A[left + m]

    for n in range(n2):
        R[n] = A[mid + n]

    # L[n1], R[n2] = [1e9] * 2
    # i, j = 0, 0
    L[n1] = 1e9
    R[n2] = 1e9
    i = 0
    j = 0

    for k in range(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

    return None


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)
    return A


if __name__ == '__main__':
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def merge(A, left, mid, right):
    global count

    L = A[left:mid] + [1e9]
    R = A[mid:right] + [1e9]

    i, j = 0, 0

    for k in range(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return None


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)
    return A


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert array_length == len(array)
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)
### BUGGY CODE ###

import sys

INF = 10e17
N = int(input())
A = list(map(int, sys.stdin.readline().rstrip().split()))
ans = 1
for i in range(N//2):
    ans = ans*A[i]*A[N-1-i]
    if ans == 0:
        print(0)
        sys.exit()
if N%2:
    ans = ans*A[N//2]
if ans > INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys

INF = 10e17
N = int(input())
A = list(map(int, sys.stdin.readline().rstrip().split()))
ans = 1
for a in A:
    if a == 0:
        print(0)
        sys.exit()
for a in A:
    ans = ans*a
    if ans > INF:
        print(-1)
        sys.exit()

print(ans)
### BUGGY CODE ###

import collections
s=input()
n=len(s)
a=[]
x=0
for i in range(n):
	j = n-1-i
	c = int(s[j])
	x += (10**i)*c
	x %= 2019
	a.append(x)
c=collections.Counter(a)
ans = 0
for k,v in c.items():
	if k==0:
		ans += v
	else:
		ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

import collections
s=input()
n=len(s)
a=[]
x=0
p=1
for i in range(n):
	j = n-1-i
	c = int(s[j])
	p %= 2019
	x += (p*c)%2019
	p *= 10
	x %= 2019
	a.append(x)
c=collections.Counter(a)
ans = 0
for k,v in c.items():
	if k==0:
		ans += v
	ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

l = raw_input().split()
s = l[0]

def get_removals(s):
    ret = []
    for i in range(len(s) - 1):
        if int(s[i]) + int(s[i + 1]) == 1:
            ret.append(i)
    return ret

def remove(s, index):
    if index == 0:
        return s[2:]
    if index == (len(s) - 1):
        return s[:index-1]
    return  s[0:index] + s[index + 2:]

num_removals = []

ones = 0
zeros = 0
for num in s:
    if num == '0':
        ones += 1
    if num == '1':
        zeros += 1
max_candidate = min(ones, zeros) * 2

def process(s, count):
    removals = get_removals(s)
    if len(removals) == 0:
        num_removals.append(count)
        if count == max_candidate:
            print(max_candidate)
            exit()
        return
    count += 2
    max_remove = 0
    ss = []
    for removal in removals:
        s1 = remove(s, removal)
        ss.append(s1)
        num_removes = len(get_removals(s1))
        if max_remove < num_removes:
            max_remove = num_removes
    for s1 in set(ss):
        if len(get_removals(s1)) == max_remove:
            process(s1, count)

process(s, 0)
print(max(num_removals))


### FIXED CODE ###

l = raw_input().split()
s = l[0]

def get_removals(s):
    ret = []
    for i in range(len(s) - 1):
        if int(s[i]) + int(s[i + 1]) == 1:
            ret.append(i)
    return ret

def remove(s, index):
    if index == 0:
        return s[2:]
    if index == (len(s) - 1):
        return s[:index-1]
    return  s[0:index] + s[index + 2:]

num_removals = []

ones = 0
zeros = 0
for num in s:
    if num == '0':
        ones += 1
    if num == '1':
        zeros += 1
max_candidate = min(ones, zeros) * 2

def process(s, count):
    removals = get_removals(s)
    if len(removals) == 0:
        num_removals.append(count)
        if count == max_candidate:
            print(max_candidate)
            exit()
        return
    count += 2
    max_remove = 0
    ss = []
    for removal in removals:
        s1 = remove(s, removal)
        ss.append(s1)
        num_removes = len(get_removals(s1))
        if max_remove < num_removes:
            max_remove = num_removes
    for s1 in set(ss):
        if len(get_removals(s1)) == max_remove:
            process(s1, count)

# process(s, 0)
print(max_candidate)
### BUGGY CODE ###

import re
n,q=map(int,input().split())
s=input()
ans=[0]*q
for i in range(q):
    l,r=map(int,input().split())
    ans[i]=len(re.findall('(AC)',s[l-1:r]))
print(*ans,sep='\n')


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
l=[0]*(len(s)+1)
for i in range(1,len(s)):
    l[i+1]=l[i]
    if s[i-1]=='A' and s[i]=='C':
        l[i+1]+=1
ans=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    ans[i]=l[b]-l[a]
print(*ans,sep='\n')
### BUGGY CODE ###

n,k=map(int,input().split())
li=list(map(int, input().split()))
max=0
for i in range(n-k+1):
  tmp=0
  for j in range(k):
    tmp+=li[i+j]
  if max <= tmp:
    max=tmp
print((max+k)/2)

### FIXED CODE ###

n,k=map(int,input().split())
li=list(map(int, input().split()))
tmp=0
for i in range(k):
  tmp+=li[i]

max=tmp
for i in range(1,n-k+1):
  tmp=tmp-li[i-1]+li[i+k-1]
  if max<=tmp:
    max=tmp
print((max+k)/2)
### BUGGY CODE ###

from itertools import product
H, W, A, B = map(int, input().split())

bins = []
for i in range(2**W):
    b = bin(i)[2:].zfill(W)
    if b.count('0') == A or b.count('1') == A:
        bins.append(b)

for rows in product(bins, repeat=H):
    for i in range(H):
        h = ''
        for r in rows:
            h += r[i]
        if h.count('0') != B and h.count('1') != B:
            break
    else:
        for r in rows:
            print(r)
        exit()
print('No')


### FIXED CODE ###

H, W, A, B = map(int, input().split())

for i in range(H):
    if i < B:
        print('1'*A + '0'*(W-A))
    else:
        print('0'*A + '1'*(W-A))
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
import itertools
flag = True
while(flag):
    count = 0
    if K in A:
        flag = False
        break
    A_2 = list(itertools.combinations(A,2))
    for comb in A_2:
        diff = abs(comb[0] - comb[1])
        if diff not in A:
            A.append(diff)
        else:
            count += 1
    else:
        if (count == len(A_2)):
            flag = False
if K in A:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')



### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
import fractions
import functools
gcd = functools.reduce(fractions.gcd, A)
A_max = max(A)
if (A_max >= K and K % gcd == 0):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

def xor(x, y):
    z = (x | y) - (x & y) 
    return z

def main():
    A, B = map(int, input().split(' '))

    res = 0
    while A < B:
        res = xor(res, A)
        A += 1
    
    res = xor(res, B)
    print(res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def xor(x, y):
    return (x | y) - (x & y)

def get_res(x):
    if x % 4 == 0:
        return x
    elif x % 4 == 1:
        return 1
    elif x % 4 == 2:
        return x + 1
    else:
        return 0

def main():
    A, B = map(int, input().split(' '))

    res_A = get_res(A - 1) if A > 0 else 0
    res_B = get_res(B)
    print(xor(res_A, res_B))    

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = [ [int(j) for j in input().split()] for _ in range(N)]

dp = [ [0] * (1<<N) for _ in range(N+1)]
dp[0][0] = 1
MOD = int(1e9+7)

for S in range(1<<N):
    i = bin(S).count("1")
    for j in range(N):
        if not (1<<j) & S and A[i-1][j] == 1: # vacant lot
            dp[i+1][S^(1<<j)] += dp[i][S] % MOD

print(dp[N][(1<<N)-1] % MOD)
            

            
    
    


### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))
### BUGGY CODE ###

S = input()

length = len(S)

cnt = 0
for x in range(length):
    temp = int(S[x : x + 4])
    for i in range(x + 4, length + 1):
        if temp % 2019 == 0:
            cnt += 1
        #print(temp, cnt)

        if i < length:
            temp = temp * 10 + int(S[i])

print(cnt)



### FIXED CODE ###

S = input()[::-1]

length = len(S)
dp = [0] * (length + 2)

times = 1
for x in range(1, length + 1):
    dp[x] += dp[x - 1]
    dp[x] %= 2019
    dp[x] += int(S[x - 1]) * times
    dp[x] %= 2019
    times *= 10
    times %= 2019


cnt = [0] * 2020
for x in range(length + 1):
    cnt[dp[x]] += 1

ans = 0
for c in cnt:
    ans += (c * (c - 1)//2)

print(ans)
### BUGGY CODE ###

K=input()
K=int(K)
import fractions
def gcd(a,b,c):
  return fractions.gcd(fractions.gcd(a,b),c)
m=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      m=m+gcd(i,j,k)
print(m)

### FIXED CODE ###

from math import gcd
K = int(input())
m = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    w = gcd(i, j)
    if w==1:
      m += K
    else:
      for k in range(1, K+1):
        m += gcd(w, k)
print(m)
### BUGGY CODE ###

N,K = map(int, input().split())
V = [int(v) for v in input().split()]


def f(L, i, n):
    if i == 0 or len(L) == 0:
        return 0
    if L[n] >= 0:
        t = L[n]
        if n >= 0:
            n += 1
        else:
            n -= 1
        return t+f(L,i-1,n)
    else:
        t = L[n]
        if n >= 0:
            n += 1
        else:
            n -= 1
        if i >= 2:
            return max(f(L, i-2, n), t+f(L, i-1, n))
        else:
            return t+f(L, i-1, n)
    

V_sort = sorted(V)
s = sum(V)
ans = 0
for i in range(1, K+1):
    if i >= N:
        c = s
        j = 0
        while j < N:
            if V_sort[j] < 0:
                c -= V_sort[j]
            else:
                j = N
            j += 1
        ans = max(ans, c)
    else:
        c = 0
        for j in range(i+1):
            c = max(c, f(V, j, 0)+f(V, i-j, -1))
        ans = max(ans, c)
        
print(ans)

### FIXED CODE ###

N,K = map(int, input().split())
V = [int(v) for v in input().split()]

ans = 0
for i in range(K+1):
    if i < N:
        for j in range(i+1):
            temp1 = V[:j]
            temp2 = V[N-(i-j):]
            temp = temp1 + temp2
            temp.sort()
            s = sum(temp)
            k = 0
            while k < len(temp) and k < K-i:
                if temp[k] < 0:
                    s -= temp[k]
                k += 1
            ans = max(ans, s)
    else:
        temp = sorted(V)
        s = sum(temp)
        j = 0
        while j < min(N, i-N):
            if temp[j] < 0:
                s -= temp[j]
            j += 1
        ans = max(ans, s)
        
print(ans)
### BUGGY CODE ###

from sys import stdin
import fractions

class SegmentTree():

    def __init__(self, n):
        self.n = 1
        # nに最も近い2のべき乗を計算
        while self.n < n:
            self.n *= 2

        self.N0 = 2**(n-1).bit_length()

        # ノードの個数は2n-1個
        # 初期化はモノイドで
        self.dat = [0] * (self.n * 2 - 1)
        
    def update(self, i, x):
        i = i + self.n - 1
        self.dat[i] = x

        while(i > 0):
            i = (i-1) // 2
            self.dat[i] = fractions.gcd(self.dat[i * 2 + 1], self.dat[i * 2 + 2])

    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        ret = 0
        
        while L < R:
            if R & 1:
                R -= 1
                ret = fractions.gcd(ret, self.dat[R-1])
                
            if L & 1:
                ret = fractions.gcd(ret, self.dat[L-1])
                L += 1
                
            L >>= 1; R >>= 1
        return ret


if __name__ == "__main__":
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    st = SegmentTree(N)
    for i in range(N):
        st.update(i, A[i])
    
    ans = - (10 ** 10)
    for i in range(N):
        if i == 0:
            leftv = 0
        else:
            leftv = st.query(0, i)
        
        if i == N-1:
            rightv = 0
        else:
            rightv = st.query(i+1, N)

        # for Debug    
        #print("**{0}** | {1} {2}".format(i, leftv, rightv))
        ans = max(ans, fractions.gcd(leftv, rightv)) 

    # for Debug
    #print(st.dat)

    print(ans)

### FIXED CODE ###

from sys import stdin
import fractions

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
# インデックスを直感で使えるように先頭にダミーを入れる
A = [0] + A

"""
L(i) := A_1, A_2, ..., A_i-1 の最大公約数
R(i) := A_i, A_i+1, ..., A_N の最大公約数
Aiを書き換えることにした場合の最大公約数をM_iとすると
M_i = gcd(L(i), R(i+1))

ただし L(0)=0, R(N+1)=0
"""

L = [0 for _ in range(N+1)]
R = [0 for _ in range(N+2)]

for i in range(N):
    L[i+1] = fractions.gcd(L[i], A[i])


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

M = []

for i in range(1, N+1):
    M_i = fractions.gcd(L[i], R[i+1])
    M.append(M_i) 

print(max(M))
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
suml = sum(l)
xs = set()
for i in range(2**n):
    x = []
    for j in range(n):
        if ((i >> j) & 1):
            x.append(l[j])
    xs.add(abs(2*sum(x) - suml))
try:
    xs.remove(0)
except:
    pass
ans = min(xs)
print(ans)

### FIXED CODE ###

from itertools import accumulate
n = int(input())
l = list(map(int,input().split()))
suml = sum(l)
accl = list(accumulate([0]+l))
ans = float('Inf')
for i in range(1,n):
    x = accl[i]
    j = abs(2*x - suml)
    ans = min(ans,j)
print(ans)