Problem:
 Score : 200 points    Problem Statement There are K pieces of cakes.
Mr. Takahashi would like to eat one cake per day, taking K days to eat them all.  There are T types of cake, and the number of the cakes of type i ( 1 ≤ i ≤ T ) is a_i .  Eating the same type of cake two days in a row would be no fun,
so Mr. Takahashi would like to decide the order for eating cakes that minimizes the number of days on which he has to eat the same type of cake as the day before.  Compute the minimum number of days on which the same type of cake as the previous day will be eaten.      Constraints  1 ≤ K ≤ 10000  1 ≤ T ≤ 100  1 ≤ a_i ≤ 100  a_1 + a_2 + ... + a_T = K         Input The input is given from Standard Input in the following format:  K  T  a_1  a_2  ...  a_T       Output Print the minimum number of days on which the same type of cake as the previous day will be eaten.        Sample Input 1 7 3
3 2 2      Sample Output 1 0  For example, if Mr. Takahashi eats cakes in the order of 2, 1, 2, 3, 1, 3, 1 , he can avoid eating the same type of cake as the previous day.       Sample Input 2 6 3
1 4 1      Sample Output 2 1  There are 6 cakes.
For example, if Mr. Takahashi eats cakes in the order of 2, 3, 2, 2, 1, 2 , he has to eat the same type of cake (i.e., type 2 ) as the previous day only on the fourth day.
Since this is the minimum number, the answer is 1 .       Sample Input 3 100 1
100      Sample Output 3 99  Since Mr. Takahashi has only one type of cake, he has no choice but to eat the same type of cake as the previous day from the second day and after.

Solution (Python):
k,t = map(int,input().split())
a = list(map(int,input().split()))
if t == 1:
  print(k-1)
else:
  print(max(0,2*max(a)-k-1))

Solution (Python):
    
K,T = list(map(int,input().split()))

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

a.sort()

ans=max(a[T-1]-sum(a[:-1])-1,0)
print(ans)

Solution (Python):
K,T=map(int,input().split())
a=list(map(int,input().split()))
print(max(0,max(a)-1-(K-max(a))))

Solution (Python):
k,t = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a)

while a != [0] * (t-1) + [a[-1]]:
    a[-2], a[-1] = 0, a[-1] - a[-2]
    a = sorted(a)

print(a[-1]-1 if a[-1]>0 else 0)

Solution (Python):
K, T = map(int, input().split())
a = list(map(int, input().split()))

print(max(0, 2*max(a)-sum(a)-1))

Solution (Python):
K, T = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
print(max(2 * max(A) - sum(A) - 1, 0))

Solution (Python):
import bisect
K, T = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
while len(A) > 1:
    A[-1] -= 1
    if A[-1] == 0:
        A = A[:-1]
    else:
        i_bisect_left = bisect.bisect_left(A[:-1], A[-1])
        if i_bisect_left == len(A) - 1:
            A = A[:-2] + [A[-1], A[-2]]
        else:
            v = A[-1]
            A = A[:-1]
            A.insert(i_bisect_left, v)
print(A[0] - 1)

Solution (Python):
k,t=map(int,input().split())
a=list(map(int,input().split()))
m=max(a)
print(max(0,m-1-(k-m)))

Solution (Python):
K,T = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
if sum(A[:-1]) >= A[-1]-1 :
    ans = 0
else :
    ans = A[-1]-1 - sum(A[:-1])
print(ans)

Solution (Python):
K, T = map(int,input().split())
a = [int(i) for i in input().split()]
am = max(a)
if am-1 <= sum(a) - am:
    print(0)
else:
    print(2*am -1 -sum(a))

Solution (Python):
K, T = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)

if T == 1:
	print(K - 1)
else:
	if 2 * a[-1] - K - 1 >= 0:
		print(2 * a[-1] - K - 1)
	else:
		print(0)

Solution (Python):
k,t = map(int,input().split())
a = list(map(int,input().split()))

while a!=[a[0]]+[0]*(t-1):
    a = sorted(a,reverse=True)
    a[0],a[1] = a[0]-a[1],0

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

Solution (Python):
k,t=map(int,input().split())
a=list(map(int,input().split()))
print(max((max(a)*2-1-k),0))

Solution (Python):
k,t=map(int, input().split())
a=list(map(int, input().split()))
a.sort(reverse=True)
m=a[0]
a=a[1:]
print(max(m-1-sum(a),0))

Solution (Python):
k,t = map(int, input().split())
list_cake = list((map(int, input().split())))
list_cake.sort()
if list_cake[-1] <= k/2:
    print(0)
else:
    print(k - (k-list_cake[-1]) * 2 - 1)

Solution (Python):
K, T = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if a[-1] - 1 <= sum(a[:-1]):
    print(0)
else:
    print(a[-1] - 1 - sum(a[:-1]))

Solution (Python):
k, t = map(int, input().split())
A = list(map(int, input().split()))

if t == 1:
    print(k-1)
    exit()

ans = 0
before = -1
for i in range(k):
    A.sort(reverse=True)
    
    if A[0] == before-1:
        if A[1] == 0:
            before = A[0]
            A[0] -= 1
            ans += 1
        else:
            before = A[1]
            A[1] -= 1
    else:
        before = A[0]
        A[0] -= 1
    before
print(ans)

Solution (Python):
k, t = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
print(max(a[-1] - sum(a[:-1]) - 1, 0))

Solution (Python):
K, T = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
print(max(0, a[-1] - sum(a[:-1]) - 1))

Solution (Python):
k,t=map(int,input().split())
*a,=map(int,input().split())
print(max(max(a)*2-k-1,0))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

K,T = inpl()
aa = inpl()
MAX = max(aa)

if MAX <= (K+1)//2:
	print(0)
else:
	zan = MAX - (K+1)//2
	if K%2 == 0:
		print(zan*2-1)
	else:
		print(zan*2)

Solution (Python):
k, t = map(int, input().split())
a = list(map(int, input().split()))
while len(a) > 1:
    a.sort()
    a[0] -= 1
    a[-1] -= 1
    while 0 in a:
        a.remove(0)
if len(a) == 0:
    print(0)
else:
    print(a[0]-1)

Solution (Python):
k,t = list(map(int,input().split()))
a = list(map(int,input().split()))
p = max(a)
res = p-1 - (k-p)
if res >= 0:
    print(res)
else:
    print(0)

Solution (Python):
K,T=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
s=sum(a)
b=s-a[0]
if b>=a[0]-1:
  print 0
else:
  print a[0]-1 - b

Solution (Python):
K, T = map(int, input().split())
A = list(map(int, input().split()))
print(max(0, (max(A)-1) - (K-max(A))))

Solution (Python):
k, t = map(int, input().split())
a = list(map(int, input().split()))
a_s = sorted(a, reverse=True)
buf = 0
for i in range(t):
    buf = abs(buf - a_s[i])
print(buf - 1 if buf > 0 else 0)

Solution (Python):
K,T=map(int,input().split())

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

answer=max(a)

print(max(0,answer-(K-answer+1)))

Solution (Python):
K, T = map(int, input().split())
A = list(map(int, input().split()))
m = max(A)
print(max(0,m-(K-m+1)))

Solution (Python):
K,T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

max_a = max(A)
print(max(max_a - 1 - (K - max_a), 0))

Solution (Python):
K,T=map(int,input().split())
cakes = list(map(int,input().split()))
maxC=max(cakes)
if maxC - 1 <= (K-maxC):
  print(0)
else:
  print(K - (2*(K-maxC) + 1))

Solution (Python):
K,T=map(int,input().split())
a=[int(i) for i in input().split()]
M=max(a)
print(max([2*M-1-K,0]))

Solution (Python):
K,T = map(int,input().split())

A = sorted(list(map(int,input().split())),reverse=True)

BOSS_CAKE = A[0] - 1
for a in A[1:]:
    BOSS_CAKE -= a
    if BOSS_CAKE<=0:
        BOSS_CAKE = 0
        break

print(BOSS_CAKE)

Solution (Python):
k,t = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
if (k+1)//2>=max(a): print(0)
else: print(2*max(a)-(sum(a)+1))

Solution (Python):
def inpl(): return list(map(int, input().split()))
K, T = inpl()
a = inpl()
print(max(max(a)*2-K-1, 0))

Solution (Python):
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))

print(max(max(a)*2-n-1,0))

Solution (Python):
import sys


k,t=map(int,input().split())
a=list(map(int,input().split()))
if(t==1):print(k-1)
else:
    eaten=-1
    ma=0
    s=sum(a)
    for i in range(s):
        nothing=1
        for j in range(len(a)):
            if(a[j]>ma and j!=eaten):
                ma=a[j]
                keep=j
                nothing=0
        
        if(nothing):
            print(max(a))
            sys.exit()
        else:
            eaten=keep
            a[eaten]-=1
            ma=0
    print(0)

Solution (Python):
def main():
    """
    一番多い数の種類のケーキから食べる
    上記と異なる種類のケーキのうち、一番多い数の種類のケーキを食べる
    以下繰り返し
        他のケーキの個数がすべて0なら連続日数として追加
    """
    K, T = map(int, input().split())
    A = map(int, input().split())

    A = list(A)
    f(K, T, A)


def f(K, T, A):
    cake_type = None
    rest_K = K
    ans = 0
    while rest_K > 0:
        bef_cake_type = cake_type
        max_a = 0
        for i, a in enumerate(A):
            if a > max_a and i != bef_cake_type:
                cake_type = i
                max_a = a

        A[cake_type] -= 1
        rest_K -= 1
        if bef_cake_type == cake_type:
            ans += 1
        

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
k,t = map(int,input().split())
lis = list(map(int,input().split()))
print(max((max(lis)-1)-(k-max(lis)),0))

Solution (Python):
K,T = map(int,input().split())
src = list(map(int,input().split()))
most = max(src)
print(max(0, most*2 - K - 1))

Solution (Python):

K, T = map(int, input().split())
a = list(map(int, input().split()))
s = 0
a.sort(reverse=True)
for i in range(1, T):
    s += a[i]

print(max(0, a[0] - s - 1))

Solution (Python):
K,T = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

num = (K - max(a))
if (max(a) - 1) > num:
    print((max(a) - 1) - num)
else:
    print(0)

Solution (Python):
K,T = map(int, input().split())

A = list(map(lambda x: -int(x), input().split()))

import heapq as hq

hq.heapify(A)

a = hq.heappop(A)

while A:
  if a == -1:
    a = hq.heappop(A)
  else:
    a = hq.heapreplace(A,a+1)

print(-a-1)

Solution (Python):
K, T = list(map(int, input().split()))

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

sa = sorted(a)

print(max(0, sa[-1]-sum(sa[:-1])-1))

Solution (Python):
line = input().split()
K = int(line[0])
T = int(line[1])
a = map(int,input().split())
print(max(0,2*max(a)-1-K))

Solution (Python):
k,t=map(int,input().split())
a=list(map(int,input().split()))
print(max(0, max(a)*2 - sum(a) -1))

Solution (Python):
import heapq

if __name__ == "__main__":
    K,T = map(int, input().split())
    data = list(map(int, input().split()))
    cake = []
    for i,x in enumerate(data):
        cake.append([x, i])
    heapq._heapify_max(cake)
    while (len(cake) > 1):
        heapq._heapify_max(cake)
        p = heapq.heappop(cake)
        q = heapq.heappop(cake)
        
        p[0] -= 1
        q[0] -= 1
        if p[0] > 0:
            heapq.heappush(cake, p)
        if q[0] > 0:
            heapq.heappush(cake, q)
    result = 0
    if len(cake) > 0:
        t = heapq.heappop(cake)
        result = t[0]
    print (max(0, result - 1))

Solution (Python):
k,t=map(int,raw_input().split())
a=max(map(int,raw_input().split()))
print max(0, a-(k-a)-1)

Solution (Python):
raw_input()
A=map(int,raw_input().split())
print~-max(2*max(A)-sum(A),1)

Solution (Python):
K,T = map(int,input().split())
a = list(map(int,input().split()))
print(max(0, max(a)*2 - K - 1))

Solution (Python):



K, T = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
m = max(a)
s = sum(a) - m
if m - s < 2:
    print(0)
else:
    print(m - s - 1)

Solution (Python):
k, t = map(int, input().split())
a = sorted(list(map(int, input().split())))
print(max(0, a[t-1]-sum(a[:t-1])-1))

Solution (Python):
k, t = map(int, input().split())
a = sorted(int(x) for x in input().split())
print(max(0, a[-1] - sum(a[:-1]) - 1))

Solution (Python):
K, T = map(int, raw_input().split())
a = map(int, raw_input().split())

print max(2 * max(a) - K - 1, 0)

Solution (Python):
K, T = map(int, raw_input().split())
a = map(int, raw_input().split())
print max(max(a) - (sum(a) - max(a) + 1), 0)

Solution (Python):
ini=map(int, raw_input().split())
kind=map(int, raw_input().split())
kind.sort()
kind.reverse()
a=0
b=0
for i in range(ini[1]):
	if i==0:
		a=kind[0]-1
		b=2
	else:
		if a>=kind[i]:
			a-=kind[i]
			if a==kind[i]:
				b+=kind[i]*2-1
			else:
				b+=kind[i]*2
		else:
			kind[i]-=a
			b+=kind[i]
			a=0

print a

Solution (Python):


k, t = map(int, raw_input().split())
ls_a = map(int, raw_input().split())

print max(2 * max(ls_a) - 1 - sum(ls_a), 0)

Solution (Python):
K,T = map(int,input().split())
a = list(map(int,input().split()))

pred = -1
ans = 0
a = [ (a[i],i) for i in range(T)]
while max(a)[0] > 0:
    a.sort()
    m,i = a[-1]
    flg = False
    for j in range(T-1,-1,-1):
        if pred != a[j][1] and a[j][0] > 0:
            a[j] = a[j][0]-1,a[j][1]
            pred = a[j][1]
            flg = True
            break
    if not flg:
        a[-1] = a[-1][0]-1,a[-1][1]
        ans += 1
        

print(ans)

Solution (Python):
import sys
i=1
t=True
nums=[]
for line in sys.stdin:
    if i%2==0:
        nums=line.split()
        index=0
        for number in nums:
        	nums[index]=int(nums[index])
        	index=index+1
        i=i+1
    else:
        i=i+1
        continue
    nums.sort()
    leng=len(nums)-1
    maxi=max(nums)
    maxnum=nums.count(maxi)
    if maxnum>=2:
        print(0)
    else:
        if leng>0:
            second=nums[0:leng]
            sum=0
            for number in second:
                sum=sum+int(number)
            diff=maxi-sum
            if diff<=1:
                print(0)
            else:
                print(diff-1)
        else:
            print(maxi-1)

Solution (Python):
k,t = [int(x) for x in raw_input().split()]
a = [int(x) for x in raw_input().split()]

a.sort()
res = a[-1] - sum(a[:-1])

if res<=1:
    print 0
else:
    print res-1

Solution (Python):
import sys

K,T = map(int, sys.stdin.readline().split())
a = map(int, sys.stdin.readline().split())

limit = K/2 + K%2
am= max(a)

if am > limit:
    print (am-1) - (K - am)                                                                                                                                                                                                           
else:
    print 0

Solution (Python):
def read():
	return [int(i) for i in input().split(" ")]
def maxInx(L, pre):
	tempM = [0, 0]
	for i in range(len(L)):
		if(L[i] > tempM[1] and i != pre):
			tempM = [i, L[i]] 
	return tempM[0] if tempM != [0, 0] else pre

(K, T) = read()
A = read()
pre = -1
sameDay = 0
for i in range(K):
	inx = maxInx(A, pre) 
	if(inx == pre):
		sameDay += 1
	A[inx] -= 1
	pre = inx
print(sameDay)

Solution (Python):
import sys
k,t=[int(i) for i in input().split()]
array=[int(i) for i in input().split()]
array.sort()
array=array[::-1]
max=array[0]
for i in range(1,len(array)):
    max-=array[i]
    if max<=0:
        print(0)
        sys.exit()
print(max-1)

Solution (Python):


import collections


def main():
    k, t = (int(x) for x in input().split())
    ctr = collections.Counter(dict(enumerate(int(a) for a in input().split())))
    pred = -1
    ans = 0
    sign = True
    for _ in range(k):
        if sign:
            mc = ctr.most_common()
        else:
            mc = ctr.most_common()[::-1]
        for k, v in mc:
            if k != pred and v > 0:
                pred = k
                ctr[k] = v - 1
                break
        else:
            ans += 1
            ctr[pred] -= 1
        sign = not sign
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
line = raw_input()
vals = map(int, line.split())
K = vals[0]
T = vals[1]
line = raw_input()
A = map(int, line.split())

def cal():
    A.sort()
    A.reverse()

    S = sum(A[1:])
    if S >= A[0] - 1:
        return 0

    return A[0] - 1 - S

print cal()

Solution (Python):
def chk_cake():
    for i in range(0, cake_kind):
        if cakes[i] > 0:
            return True
    return False


def get_max(last_cake):
    max_num = 0
    max_inx = last_cake
    for i in range(0, cake_kind):
        if max_num < cakes[i] and i != last_cake:
            max_num = cakes[i]
            max_inx = i
    return max_inx

counter = 0
cake_num, cake_kind = map(int, raw_input().split())
cakes = map(int, raw_input().split())

last_cake = -1
while chk_cake():
    i = get_max(last_cake)
    cakes[i] = cakes[i] - 1
    if i == last_cake:
        counter += 1
    last_cake = i

print counter

Solution (Python):
def f():
    line = list(map(int, input().split()))
    k = line[0]
    t = line[1]
    a = list(map(int, input().split()))
    a.sort()

    if t == 1:
        return k-1
    if t == 2:
        return a1-a0-1
    a = [0] + a
    n1 = a[-1] - a[-2]
    n2 = 1
    for i in range(1, t-1):
        n2 = n2 + (a[i]-a[i-1])*(t-i-1)
    if n1 < n2:
        return 0
    else:
        return n1 - n2

print (f())

Solution (Python):

def getMax(a, b):
    if a > b:
        return a
    return b

def getCakeRepeats(cakes):
    front_iter = 0
    back_iter = len(cakes) - 1

    while back_iter > front_iter:
        if cakes[back_iter] < cakes[front_iter]:
            cakes[front_iter] -= cakes[back_iter]
            cakes[back_iter] = 0
            back_iter -= 1
        elif cakes[back_iter] > cakes[front_iter]:
            cakes[back_iter] -= cakes[front_iter]
            cakes[front_iter] = 0
            front_iter += 1
        else:
            cakes[back_iter] = 0
            cakes[front_iter] = 0
            back_iter -= 1
            front_iter += 1

    return getMax(0, sum(cakes) - 1)

if __name__ == "__main__":
    setup = raw_input()
    cakes = list(map(int, raw_input().split()))
    print getCakeRepeats(sorted(cakes))

Solution (Python):
[K, T] = map(int, raw_input().split(' '))
cakes = map(int, raw_input().split(' '))

print max(0, 2 * max(cakes) - sum(cakes) - 1)

Solution (Python):
K, T = map(int,input().split())
list = list(map(int, input().split()))

list.sort()
if T > 1:
        p = list[-1] - list[-2]

        sum = 0
        for k in list[:-2]:
                sum += k

        if p - sum <= 1:
                print(0)
        else:
                print(p - sum - 1)
else:
        print(K-1)

Solution (Python):


import copy
K,T=map(int,raw_input().split())
arr=map(int,raw_input().split())

yesterday=-1
nokori1=False
for i in range(K):
    
    mai=arr.index(max(arr))
    if yesterday!=mai:
        arr[mai]-=1     
        yesterday=mai
        
    else:
        for j in range(len(arr)+1):
            if j==len(arr):
                nokori1=True
                break
            if arr[j]>0 and yesterday!=j:
                arr[j]-=1
                yesterday=j
                
                break
    if nokori1:
        break
ans=0
if arr.index(max(arr))==yesterday:
    ans=max(arr)
else:
    ans=max(arr)-1
if ans==-1:
    ans+=1
print ans

Solution (Python):
k, t = map(int, raw_input().split())
a = map(int, raw_input().split())
a = sorted(a,reverse=True)
b = range(len(a))
c = a[:]
a = []
for i in xrange(len(b)):
    a.append([c[i], i])
d = 0
y = -1
while True:
    
    
    if len(a) == 1:
        d += a[0][0]-1
        break
    else:
        if a[0][0] == 0:
            break
        elif a[0][1] != y:
            a[0] = [a[0][0]-1,a[0][1]]
            y = a[0][1]
        else:
            if a[1][0] == 0:
                d += a[0][0]
                break
            a[1] = [a[1][0]-1,a[1][1]]
            y = a[1][1]
        a = sorted(a,reverse=True)






print d

Solution (Python):
k,t=map(int,input().split())
arr=list(map(int,input().split()))
amax = max(arr)
arest = k-amax
if arest>=amax-1:
    print(0)
else:
    print(amax-1-arest)

Solution (Python):
l=list(map(int, input().split()))
r=list(map(int, input().split()))
print(max(0,2*max(r)-l[0]-1))

Solution (Python):
cakeNum, dayNum = map(int, raw_input().split(' '))
cakes = []
map(cakes.append, map(int, raw_input().split(' ')))

if max(cakes) * 2 > sum(cakes):
	print max(cakes) * 2 - sum(cakes) - 1
else:
	print 0

Solution (Python):
input = raw_input().split(' ')
K = int(input[0])
T = int(input[1])
input = raw_input().split(' ')
max_num = 0
sum_num = 0
for i in range(0, T):
  temp = int(input[i])
  if max_num < temp:
    max_num = temp
  sum_num += temp

if max_num <= sum_num - max_num + 1:
  print "0"
else:
  print max_num - (sum_num - max_num) - 1

Solution (Python):
K, T = map(int, input().split())
A = list(map(int, input().split()))

if T == 1:
    print(A[0] - 1)
    exit()

prev_argmax = -1
for k in range(K):
    if prev_argmax == -1:
        temp_max = -1
        for i, a in enumerate(A):
            if a > temp_max:
                temp_max = a
                argmax = i
    else:
        temp_max = -1
        for i, a in enumerate(A):
            if i != prev_argmax:
                if a > temp_max:
                    temp_max = a
                    argmax = i
        if temp_max == -1:
            temp_max = max(A[:prev_argmax] + A[prev_argmax + 1:])
            for i, a in enumerate(A):
                if i != prev_argmax and a == temp_max:
                    argmax = i
                    break
    if temp_max == 0:
        break
    A[argmax] -= 1
    prev_argmax = argmax
ans = 0
for i, a in enumerate(A):
    if i != prev_argmax:
        ans += max(0, a - 1)
    else:
        ans += max(0, a)
print(ans)

Solution (Python):
k,t=map(int,input().split())
a=[int(i) for i in input().split()]
m=2*max(a)-sum(a)
print(0 if m<=1 else m-1)

Solution (Python):
import collections

k, t = [int(x) for x in input().split()]
a = collections.Counter(dict(enumerate([int(x) for x in input().split()])))

last = None
ans = 0
for i in range(k):
    mc = a.most_common(2)

    if len(mc) == 1 or mc[1][1] == 0 or mc[0][0] != last:
        now = mc[0][0]
    else:
        now = mc[1][0]

    ans += last == now
    a[now] -= 1
    last = now

print(ans)

Solution (Python):
s = input()
nums = [int(x) for x in input().split()]
mx = max(nums)
remain = sum(nums) - mx
print(0 if mx-remain <= 0 else mx-remain-1)

Solution (Python):
k, t = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a.sort()
a.reverse()
same_eaten = 0

a[0] -= 1
last_index = 0
k -= 1
for _ in range(k):
    eaten = False
    for i in range(len(a)):
        if i != last_index and a[i] > 0:
            eaten = True
            a[i] -= 1
            if a[i+1] > a[i]:
                last_index = i+1
            else:
                last_index = i
            a.sort()
            a.reverse()
            break
    if not eaten:
        same_eaten += 1
print(same_eaten)

Solution (Python):
def main():
    K, T = map(int, input().split())
    a = list(map(int, input().split()))

    previous_value = -1
    result = []
    for i in range(K):
        max_a = -1
        for (index, value) in enumerate(a):
            if max_a < value and previous_value != index and value > 0:
                max_a = value
                next_value = index
        a[next_value] -= 1
        result.append(next_value)
        previous_value = next_value

    r = 0
    for i in range(K-1):
        if result[i] == result[i+1]:
            r+=1
    print(r)



if __name__ == '__main__':
    main()

Solution (Python):

from sys import stdin
import numpy as np
n = stdin.readline()
n = n.strip().split(" ")
K = int(n[0])
T = int(n[1])
n = stdin.readline()
n = n.strip().split(" ")
a = []
for t in n:
	a.append(int(t))

idx = np.argmax(a)

res = np.max(a) -1
for b in range(len(a)):
	if b != idx:
		res -= a[b]
if res < 0:
	res = 0
print res

Solution (Python):
k,t=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
for i in xrange(t):
    j=t-1
    while 1:
        if i==j:
            if a[i]-1<0:
                print(0)
            else:
                print(a[i]-1)
            exit()
        if a[j]>=a[i]:
            a[j]-=a[i]
            break
        else:
            a[i]-=a[j]
            a[j]=0
            j-=1

Solution (Python):
k, t = map(int, raw_input().split())

a = map(int, raw_input().split())

m = max(a)

print max(m*2 - k -1, 0)

Solution (Python):
k, t = map(int, raw_input().split())
a = map(int, raw_input().split())

while len(a) > 1:
    a.sort()
    tmp = abs(a.pop() - a.pop())
    if tmp:
        a.append(tmp)

if not a:
    print 0
else:
    print a[0] - 1

Solution (Python):
k,n = map(int, raw_input().split())
a = map(int, raw_input().split())

m = max(a) - 1
rest = sum(a) - max(a)
print m - rest if m - rest >= 0 else 0

Solution (Python):
K,T = map(int,raw_input().split())
A = map(int,raw_input().split())

A.sort()
A.reverse()
print max(A[0]-sum(A[1::])-1,0)

Solution (Python):
K, T = map(int, input().split())
a = list(map(int, input().split()))

ans = 0

x = -1
for i in range(K):
    m1 = -1
    m2 = -1
    i1 = -1
    i2 = -1
    for j in range(len(a)):
        if a[j] > m1:
            i2 = i1
            i1 = j
            m2 = m1
            m1 = a[j]
        elif a[j] > m2:
            m2 = a[j]
            i2 = j
    if x != i1 and m1 > 0:
        a[i1] -= 1
        x = i1
    elif x != i2 and m2 > 0:
        a[i2] -= 1
        x = i2
    else:
        ans += 1
print(ans)

Solution (Python):
k, t = map(int, input().split())
a = [int(i) for i in input().split()]
m = max(a)
print(max(2 * m - k - 1, 0))

Solution (Python):
K, T = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)-max(a)
if max(a) - s < 2:
	print(0)
else:
	print(max(a)-s-1)

Solution (Python):

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    k, t = reads()
    a = [list(x) for x in list(enumerate(reads()))]
    n = -1
    c = 0
    while sum([x[1] for x in a]):
        a = sorted(a, key=lambda x:x[1], reverse=True)
        if a[0][0] != n:
            n = a[0][0]
            a[0][1] -= 1
        else:
            if len(a) == 1:
                c += 1
                a[0][1] -= 1
            elif 0 < a[1][1]:
                a[1][1] -= 1
                n = a[1][0]
            else:
                a[0][1] -= 1
                c += 1
    print(c)

main()

Solution (Python):


import re

K, T = map(int, input().split())
a = list(map(int, input().split()))

count = 0
n = None 
for j in range(K):
    m = 0
    t = None
    for i,c in enumerate(a):
        if c > m and (n is None or i != n):
            m = c
            t = i
    if t is None:
        count += 1
        t = n
    a[t] -= 1
    n = t
print(count)

Solution (Python):
k, t = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = 0
mx = max(a)
if mx*2 > k+1:
    ans = mx*2-k-1
print ans

Solution (Python):
k,t=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
a.sort(reverse=True)
if len(a) ==1 :
    print(k-1)
else:
    m = 0
    for i in a:
        if(m<i):
            m = i - m
        else:
            m = m - i
    print(max(m-1,0))

Solution (Python):
import numpy as np


K, T = map(int, input().split())
A = list(map(int, input().split()))
A = [(a, i) for i, a in enumerate(A)]

def main():
    if len(A) < 2:
        return K - 1
    s = -1
    answer = 0
    for k in range(K):
        A.sort(reverse=True)
        a, i = A[0]
        b, j = A[1]

        if i != s:
            A[0] = (a - 1, i)
            s = i
            continue

        if b == 0:
            A[0] = (a - 1, i)
            s = i
            answer += 1
            continue

        A[1] = (b - 1, j)
        s = j
    return answer

print(main())

Solution (Python):
K, T = map(int, raw_input().split())

a = map(int, raw_input().split())

ans = 2 * max(a) - K - 1

if ans < 0:
    print 0
else:
    print ans

Solution (Python):
K, T = map(int, raw_input().split())
nums = [int(t) for t in raw_input().split()]

max_1 = max(nums)
nums.remove(max_1)
sum_remain = sum(nums)
if sum_remain >= max_1-1:
    print 0
else:
    print (max_1 - sum_remain - 1)

Solution (Python):
K, T = map(int, input().split())
a = list(map(int, input().split()))

if T == 1:
    print(K - 1)
else:
    max_ai = max(a)
    slit = max_ai - 1
    if slit > sum(a) - max_ai:
        print(slit - (sum(a) - max_ai))
    else:
        print(0)

Solution (Python):
k, t = list(map(int, input().split()))
a = list(map(int, input().split()))

M = max(a)
print(max(0, 2*(M-(k//2+1))+1-k%2))

Solution (Python):
import sys

K, T = map(int, sys.stdin.readline().split())
As = list(map(int, sys.stdin.readline().split()))

a = max(As)
b = a - (K - a)

if b >= 1:
    print(b-1)
else:
    print(0)

Solution (Python):
n, k = map(int, raw_input().split())
a = map(int, raw_input().split())
x = max(a)
x = x - (n - x) - 1
if k == 1:
   x = a[0] - 1
print max(x, 0)

Solution (Python):
def solve():
    total, num_types = map(int, raw_input().split())
    type_counts = sorted(map(int, raw_input().split()))
    big = type_counts[-1]
    rest = total - big
    return max(0, big - rest - 1)

if __name__ == '__main__':
    print(solve())

Solution (Python):
K, T = list(map(int,input().split()))
a = list(map(int,input().split()))

a.sort()

maxi = a[-1]
if K /2>= maxi+1:
    print(0)
    exit()

ans =None
if K%2==0:
    ans =(maxi - K//2)*2 -1

else:
    ans = (maxi - K//2 - 1)*2
if ans<0:
    ans=0


print(ans)

Solution (Python):
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')


def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
def join(s):
    return ''.join(s)


def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

nh=zip([1,0,-1,0],[0,1,0,-1])
mod=1000000007


k,t=ii()
a=ii()
cur=a.index(max(a))
a[cur]-=1
cnt=0
for j in range(k-1):
    tmp=[a[j] for j in range(t) if j!=cur and a[j]!=0]
    if len(tmp)!=0:
        cur=a.index(max(tmp))
        a[cur]-=1
    else:
        a[cur]-=1
        cnt+=1
print cnt

Solution (Python):
kt = list(map(lambda number: int(number), input().split(' ')))
a_list = list(map(lambda number: int(number), input().split(' ')))

a_list.sort(reverse=True)

remain = kt[0] - a_list[0]
print(max(-1 * (remain + 1 - a_list[0]), 0))

Solution (Python):
from collections import Counter
K, T = [int(x) for x in raw_input().strip().split()]
a = [int(x) for x in raw_input().strip().split()]
amax = max(a)
aothersum = sum([x for x in a if x!=amax])
ac = Counter(a)
aothersum += (ac[amax]-1)*amax

if amax <= aothersum:
  print 0
else:
  print amax - aothersum - 1

Solution (Python):
from functools import reduce
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
s = reduce(lambda sum,x: sum+x, a)
m = max(a)
x = m - (s-m)
if x > 0:
    print(x-1)
else:
    print(0)

Solution (Python):
K, T = list(map(int, input().split()))
a = list(map(int, input().split()))













print(max(0,max(a)*2-sum(a)-1))

Solution (Python):
K, T = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]


def argmax(l, excep):
    m = -1
    ix = -1

    for i, e in enumerate(l):
        if i == excep:
            continue

        if e > m:
            m = e
            ix = i

    return ix, m


t = sum(a)
b = -1
ans = 0

for i in range(t):
    ix, m = argmax(a, b)

    if m > 0:
        b = ix
        a[ix] -= 1

    else:
        if b == -1:
            break

        if a[b] != 0:
            ans += 1
            a[b] -= 1
        else:
            break

print(ans)