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, raw_input().split())
A = map(int, raw_input().split())
A = sorted([[i, j] for i, j in enumerate(A)], key=lambda x:x[1])
last = -1
for i in xrange(K):
    A = sorted(A, key=lambda x:x[1])
    if len(A) == 1:
        print A[0][1] - 1 + (last == A[0][0])
        exit()
    if last == A[-1][0]:
        A[-2][1] -= 1
        last = A[-2][0]
        if A[-2][1] == 0:
            A.pop(-2)
    else:
        A[-1][1] -= 1
        last = A[-1][0]
        if A[-1][1] == 0:
            A.pop()
print 0

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

a = max(A)
b = K
if K%2 == 1:
    b+=1

if (b/2 >= a):
    print 0
else:
    c = K-a
    
    z = a - c - 1
    print z

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

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

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

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

Solution (Python):

import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9


def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

K, T = ln()
A = ln()

A.sort(reverse=True)

f = A[0]
S = sum(A) - f

print max(0, f - S - 1)

Solution (Python):



from __future__ import division, print_function, absolute_import, unicode_literals

import sys

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

if T == 1:
    print(a[-1]-1)
    sys.exit()
maxc = a[-1] - sum(a[:-1]) - 1
print(max(maxc, 0))

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

a_max = max(a_list)
if 2*a_max - 1 <= K:
    print 0
else:
    print (2*a_max - 1) - K

Solution (Python):
from random import random
import math
import re
import fractions

K, T = map(int, raw_input().split(" "))
A = map(int, raw_input().split(" "))
s = 0
m = 0
for a in A:
    s += a
    m = max(a, m)
print max(m * 2 - s - 1, 0)

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

Solution (Python):
K, T = map(int, input().split())
A = max(map(int, input().split()))
if A <= K // 2 + K % 2:
    print(0)
elif T == 1:
    print(K-1)
elif K % 2 == 0:
    print((A - K // 2) * 2 - 1)
else:
    print((A - K // 2 + 1) * 2)

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

cnt = collections.Counter(a)
m = max(cnt)
if m<=  k-m+1:
    print(0)
else:
    print(2*m-k-1)

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

Solution (Python):



def rl(s): return xrange(len(s))


INF = 2147483647


import sys
stdin = sys.stdin


K, T = map(int, stdin.readline().strip().split())
aa = map(int, stdin.readline().strip().split())

aa.sort()
m = aa[-1]

can_fit = (K + 1) // 2
m -= can_fit
rr = 0
if m > 0:
    if K % 2 == 0:
        rr += 1
        m -= 1
    rr += m*2

print rr

Solution (Python):

import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

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

A = [[-ai, i] for i, ai in enumerate(a)]
heapq.heapify(A)
ans = 0
b = -1
for i in xrange(K):
    t = heapq.heappop(A)
    if t[1] == b and A:
        u = heapq.heappop(A)
        if u[0] < -1:
            heapq.heappush(A, [u[0] + 1, u[1]])
        b = u[1]
        heapq.heappush(A, t)
    else:
        if t[1] == b:
            ans += 1
        if t[0] < -1:
            heapq.heappush(A, [t[0] + 1, t[1]])
        b = t[1]
print ans

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

Solution (Python):


import heapq

K,T = map(int,input().split())
As = list(map(int,input().split()))
mx = max(As)
others = K - mx
print(max(mx - 1 - others, 0))

Solution (Python):
k = int(raw_input().split()[0])
a = [int(a) for a in raw_input().split()]
ans = 0
for a in a:
  if k - a < a:
    ans = a - (k - a) - 1
print ans

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

a = raw_input()
a = [int(i) for i in a.split()]

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def f():
    k,t = list(map(int, input().split()))
    a = list(map(int, input().split()))
    s = sum(a)
    m = max(a)
    return max((m-(s-m)-1), 0)

print(f())

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

if t == 1:
    print  k - 1
    import sys
    sys.exit()

m = max(a)
p = a.index(m)

k -= 1
a[p] -= 1

while k:
    m = max(a[:p] + a[p + 1:])
    if m == 0:
        break
    p = a.index(m)
    k -= 1
    a[p] -= 1

print max(a)