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):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N,M = IL()
L = IL()
L.sort()

if L[-1] <= -(-N//2):
  print(0)
else:
  if N%2:
    print((L[-1]+(-N//2))*2)
  else:
    print((L[-1]+(-N//2))*2-1)

Solution (Python):
K,T = map(int, input().split())
a = list(map(int, input().split()))
lis = [0] * K
d = -1
T2 = T
for i in range(K):
    if T2 == 1:
        for j in range(T):
            if a[j] > 0:
                val = j
        lis[i] = val
    else:
        val = [0,0]
        for j in range(T):
            if j == d:
                continue
            if a[j] > val[0]:
                val = [a[j],j]
        a[val[1]] -= 1
        if a[val[1]] == 0:
            T2 -= 1

        lis[i] = val[1]
        d = val[1]


ans = 0
for i in range(1,K):
    if lis[i] == lis[i-1]:
        ans += 1
print(ans)

Solution (Python):



def main():
    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    x=A[0]
    print(max(x-1-(K-x),0))

if __name__ == '__main__':
    main()

Solution (Python):
import sys

K, T = map(int, input().split())
A = list(map(lambda x, y: [int(x), y], sys.stdin.readline().rsplit(), range(T)))
A.sort(reverse=True)

if T == 1:
    print(K - 1)
    exit()

res = 0
pre = -1
t = []
for k in range(K):
    if pre != A[0][1]:
        A[0][0] -= 1
        pre = A[0][1]
    elif pre == A[0][1] and A[1][0] > 0:
        A[1][0] -= 1
        pre = A[1][1]
    else:
        res += 1
    A.sort(reverse=True)

print(res)

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

if __name__ == "__main__":
    main()

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

Solution (Python):
import heapq

buf = []
heapq.heapify(buf)

k,t = map(int,input().split())
arr = list(map(int,input().split()))

for a in arr:
    heapq.heappush(buf,-a)

ans = 0

bef = None
while True:
    if not bef and len(buf) == 0:
        break
    if len(buf) == 0:
        ans += abs(bef)
        break
    else:
        top = heapq.heappop(buf)
        if bef:
            heapq.heappush(buf,bef)

        if top == -1:
            bef = None
        else:
            top += 1
            bef = top




    


print(ans)

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

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

for i in range(k):
    [nex,ful] = sorted(a)[-2:]
    ful_index,nex_index = a.index(ful),a.index(nex)
    if nex == 0:
        ans = k-i-1
        break
    if last == ful_index:
        last = nex_index
        a[nex_index] -= 1
    else:
        last = ful_index
        a[ful_index] -= 1
        
print(ans)

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

maxi = max(a)
wa = sum(a)
print(max(0, maxi-1-(wa-maxi)))

Solution (Python):
k,t = map(int,input().split())
a_list = list(map(int,input().split()))
a_max = a_list.pop(a_list.index(max(a_list)))

if t == 1:
  print(k-1)
  
else:
  if a_max - 1 >= sum(a_list):
    print(a_max - 1 - sum(a_list))
  else:
    print(0)

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

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

a = max(As)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k, t = map(int, input().split())
    A = list(map(int, input().split()))
    etc = sum(A) - max(A)
    res = max(0, max(A) - 1 - etc)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):



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


a_nums = sorted(a_nums, reverse=True)
a_max = a_nums.pop(0)
a_sum = sum(a_nums)


check = a_max - a_sum - 1
if check>=0:
    print(check)
else:
    print(0)

Solution (Python):
n, m = map(int, input().split())
data = list(map(int, input().split()))
ans = max(data)
print(max(0, 2*ans-n-1))

Solution (Python):
K,T = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
a = A[0]
if a<=(K+1)//2:
    ans = 0
elif K%2==1:
    ans = (a-(K+1)//2)*2
else:
    ans = (a-(K+1)//2)*2-1
print(ans)

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

ans = A[0]-1
for a in A[1:]:
    ans -= a
    if ans < 0:
        ans = 0
        break
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

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

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

Amax = max(A)
Asum = sum(A) - Amax

ans = max(0, Amax - Asum - 1)
print(ans)

Solution (Python):
k, t = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
if t == 1:
    print(k-1)
    exit()

x = A[0]
s = sum(A)-A[0]
if s >= x:
    print(0)
else:
    ans = x-s-1
    print(max(ans, 0))

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

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

if len(l) == 0:
    print(l[0]-1)
    exit()

m = max(l)
s = sum(l)-m

if m-1 > s:
    print(m-s-1)
else:
    print(0)

Solution (Python):
'''
from math import gcd
from itertools import accumulate, combinations, permutations, product
from bisect import bisect, bisect_left
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop
from functools import reduce
from operator import add, mul, sub, truediv, floordiv, mod

from decimal import *
getcontext().prec = 500

import string
ascii = string.ascii_lowercase
'''
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    K, T = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort(reverse=1)
    cake = []
    x = []
    n = (K + 1) // 2
    for i in range(T):
        if A[i] > n:
            cake += [i] * n
            x += [i] * (A[i] - n)
        else:
            cake += [i] * A[i]
    cake += x
    turn = [0] * K
    j = 0
    for i in range(0, K, 2):
        turn[i] = cake[j]
        j += 1
    for i in range(1, K, 2):
        turn[i] = cake[j]
        j += 1
    ans = 0
    for i in range(1, K):
        ans += turn[i-1] == turn[i]
    print(ans)


main()

Solution (Python):
n,k=map(int,input().split())
l=list(map(int,input().split()))
x=max(l)
if (n+1)//2+1>x:
  print(0)
else:
  print(x-1-(sum(l)-x))

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

Solution (Python):
def main():
    k, t = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()
    print(max(0, A[-1] - 1 - sum(A[:-1])))

if __name__ == '__main__':
    main()

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

Solution (Python):
import sys
input = sys.stdin.readline


def read():
    K, T = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return K, T, A


def solve(K, T, A):
    if T == 1:
        return K-1
    A.sort()
    return max(A[-1] - sum(A[:-1]) - 1, 0)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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

Solution (Python):
import sys
import numpy as np
K, T = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort(reverse=True)
ans = A[0] - 1
for a in A[1:]:
    ans = max(0, ans - a)
print(ans)

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

A = sorted(A, reverse=True)
while len(A) > 1:
    A[0] -= 1
    A[-1] -=1
    if A[0] == 0:
        del A[0]
    if A[-1] == 0:
        del A[-1]

if A:
    print(A[0]-1)
else:
    print(0)

Solution (Python):
import heapq

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

hp = []
heapq.heapify(hp)
for i in input().split():
    heapq.heappush(hp, -int(i))

pre = -heapq.heappop(hp) - 1  
while hp:
    q = -heapq.heappop(hp)
    if pre > 0:
        heapq.heappush(hp, -pre)
    pre = q - 1
print(pre)

Solution (Python):
from statistics import median


from fractions import gcd
from itertools import combinations 
from collections import deque
from collections import defaultdict
import bisect










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

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
k,t = readInts()
cake = readInts()
cake = sorted(cake)
if cake[-1] <= k/2:
    print(0)
else:
    print(k - (k- cake[-1]) * 2 - 1)

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

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

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





def main():
    k, t = ns()
    a = na()
    a.sort()

    total = sum(a)-a[-1]

    ans = max(0, a[-1]-total-1)

    print(ans)



if __name__ == '__main__':
    main()

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

for i,an in enumerate(a):
    b.append([an,i])
ex = -1
ans = 0

if T == 1:
	print(K-1)
else:
  for i in range(K):
    list.sort(b, reverse=True)
    if ex == b[0][1] and b[1][0] != 0:
      b[1][0] -= 1
      ex = b[1][1]
      if b[0][1] == 0 and b[1][1] == 0:
        break
    else:
      b[0][0] -= 1
      if ex == b[0][1]:
        ans+=1
      ex = b[0][1]
      if b[0][1] == 0 and b[1][1] == 0:
        break
  print(ans)

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

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

Max = max(A)

print(max(Max-1-(K-Max),0))

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

Solution (Python):
num_cakes, num_kinds = map(int,input().split())
kinds_ls = list(map(int, input().split()))
kinds_ls.sort()
max_value = kinds_ls[-1] - 1
else_sum = sum(kinds_ls[:num_kinds-1])

print(max(max_value-else_sum,0))

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

Solution (Python):
n,t,*a=map(int,open(0).read().split())
from math import *
print(max(0,(max(a)-ceil(n/2))*2-1))

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

maxi=max(a)
other = sum(a)-maxi


if maxi<=other:
    print(0)
else:
    print(maxi-other-1)

Solution (Python):
k,t=map(int,input().split())
a=list(map(int,input().split()))
sm=sum(a)
n=1
for i in a:
    if i>sm//2:
        n=i-(sm-i)
        break
print(n-1)

Solution (Python):
k, t = map(int, input().split())
dat = list(map(int, input().split()))
dat.sort(reverse=True)
prev = -1
res = 0
eat = 0
if len(dat) == 1:
    print(dat[0] - 1)
else:
    dat.sort(reverse=True)
    while dat[1] != 0:
        x = dat[1]
        dat[0] -= x
        dat[1] = 0
        dat.sort(reverse=True)
    if dat[0] == 0:
        print(0)
    else:
        print(dat[0] - 1)

Solution (Python):
def m():
    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    a = A[0]
    b = sum(A[1:])
    if (a-b) <= 1:
        return 0
    else:
        return (a-b)-1


print(m())

Solution (Python):
import sys

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

if t == 1:
    print(sum(a) - 1)
    sys.exit()

max_a = max(a)

if (sum(a) + 1) // 2 >= max_a:
    print(0)
else:
    print(2 * max_a - sum(a) - 1)

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

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

print(2*max(A)-K-1 if 2*max(A)-K>0 else 0)

Solution (Python):
import heapq
k,t = map(int,input().split())
a = list(map(int,input().split()))
mx = max(a)
others = k - mx
if t == 1:
    print(k - 1)
    exit()

if others >= mx - 1:
    print(0)
else:
    print(mx - others - 1)

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

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

Solution (Python):
k, t = map(int, input().split())
a = [int(_) for _ in input().split()]

if t == 1:
    print(k-1)
else:
    a.sort(reverse=True)
    num = a[0] - 1
    cnt = 0
    for i in range(1, t):
        cnt += a[i]
    print(max(num-cnt, 0))

Solution (Python):
from sys import stdin

def main():
    import heapq
    input = stdin.readline
    input()
    a = [-1 * int(i) for i in input().split()]
    heapq.heapify(a)
    while len(a) > 1:
        u = heapq.heappop(a)
        v = heapq.heappop(a)
        if u + 1 < 0:
            heapq.heappush(a, u + 1)
        if v + 1 < 0:
            heapq.heappush(a, v + 1)
    if len(a) == 0:
        print(0)
    else:
        print(abs(a[0] + 1))
main()

Solution (Python):
from sys import stdin

def main():
    input = stdin.readline
    k, _ = map(int, input().split())
    a = max(map(int, input().split()))
    print(max(0, 2 * a - k - 1))
main()

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

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

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

Solution (Python):
k,t,*a=map(int,open(0).read().split())
a.sort()
x=a[0]
ans=a[0]
for i in range(1,t):
  if x<a[i]:
    ans=+(a[i]-x)
  else:
    ans=0
  x+=a[i]
print(max(ans-1,0))

Solution (Python):
K, T = map(int, input().split())
A = list(map(int, input().split()))
ma = max(A)
if ma <= K//2:
    print(0)

else:
    print(ma - (K - ma + 1))

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

Solution (Python):
k,t = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
for i in range(t):
    a[i] = -a[i]
import heapq
heapq.heapify(a)
buf = heapq.heappop(a)+1
while len(a)>0:
    x = heapq.heappop(a)
    if buf!=0:
        heapq.heappush(a,buf)
    buf = x+1
print(-buf)

Solution (Python):
k,t = map(int,input().split())
A = list(map(int,input().split()))
M = max(A)
Os = sum(A)-M
if Os+1 >= M:
    print(0)
else:
    print(M-1-Os)

Solution (Python):
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    K, T = ZZ()
    A = ZZ()
    output = 0
    for a in A: output += max(0, a - (K - a + 2) + 1)
    print(output)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
k, t = map(int, input().split())
a = list(map(int, input().split()))
a = [-i for i in a]
heapq.heapify(a)
while len(a) > 1:
    m = heapq.heappop(a)
    while m < 0 and len(a) > 0:
        n = heapq.heappop(a)
        if n <= m:
            heapq.heappush(a, n-m)
            m = 0
        else:
            m -= n
    if m < 0:
        heapq.heappush(a, m)
res = heapq.heappop(a)

print(max(-res-1, 0))

Solution (Python):
import sys

def main():
  n, t, *a = map(int, sys.stdin.read().split())
  a.sort()
  b = sum(a) - a[-1]
  a = a[-1]
  ans = max(0, a-(b+1))
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
def min_day(A,K,T):
    if T == 1:
        return K-1
    else:
        A_max = max(A)
        if A_max <= K - A_max:
            return 0
        else:
            return K-2*(K-A_max)-1

def main():
    K,T = map(int,input().split())
    A = list(map(int,input().split()))

    print(min_day(A,K,T))

if __name__ == "__main__":
    main()

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

if t == 1:
    print(k-1)
else:
    m = max(a)
    print(max(m-1-(k-m), 0))

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

ans = 0
pre_index = 10**5
for i in range(k):
    max_value = 0
    max_index = 0
    for j in range(len(a)):
        if a[j] > max_value:
            max_value = a[j]
            max_index = j
    
    if pre_index != max_index:
        a[max_index] -= 1
        pre_index = max_index
    else:
        second_max_value = 0
        second_max_index = 0
        for j in range(len(a)):
            if j != max_index and a[j] > second_max_value:
                second_max_value = a[j]
                second_max_index = j
        if second_max_value == 0:
            a[max_index] -= 1
            pre_index = max_index
            ans += 1
        else:
            a[second_max_index] -= 1
            pre_index = second_max_index

print(ans)

Solution (Python):
import heapq

def main():
    K, T = map(int, input().split())
    a = list(map(int, input().split()))
    if T == 1:
        print(K-1)
        return
    b = [-x for x in a]
    heapq.heapify(b)
    tmp = heapq.heappop(b)
    for i in range(K):
        tmp2 = heapq.heappop(b)
        if tmp2 == 0:
            break
        heapq.heappush(b, tmp+1)
        tmp = tmp2
    print(K-1-i)
    
if __name__ == "__main__":
    main()

Solution (Python):
import heapq
k,t = map(int,input().split())
a = list(map(int,input().split()))
pre = a.index(max(a))
res = 0
while k>0:
    a[pre] -=1
    k -=1
    if k==0:
        break
    else:
        Conf=[]
        Conf = a[:]
        if t>1:
            Conf[pre] = -1
            preV = max(Conf)
            prei = a.index(preV)
            if preV==0:
                res+=1
            else:
                pre = prei
        else:
            res+=1
print(res)

Solution (Python):


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

if T == 1:
    count = K - 1
elif T == 2:
    diff = a_list[-1] - a_list[-2]
    if diff <= 1:
        count = 0
    else:
        count = diff - 1
else:
    
    diff = a_list[-1] - a_list[-2]
    if diff <= 1:
        count = 0
    else:
        x = sum(a_list[:-2])
        if (a_list[-1] - 1) <= (a_list[-2] + x):
            count = 0
        else:
            count = a_list[-1] - (a_list[-2] + x) - 1
ans = count
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    K,T=map(int,input().split())
    A=list(map(int,input().split()))

    mv=max(A)
    mi=A.index(mv)

    rem=sum(A)-mv
    print(max(0,mv-1-rem))
    

    

    
resolve()

Solution (Python):
from heapq import heapify, heappop, heappush
k, t = map(int, input().split())
a = list(map(int, input().split()))

que = []
heapify(que)

for i in range(t):
    heappush(que, (-a[i], i))

s = [-1]
while len(que) > 0:
    if len(que) == 1:
        a_i, idx = heappop(que)
        for _ in range(-a_i):
            s.append(idx)
        break
    else:
        a_i, idx_i = heappop(que)
        if s[-1] == idx_i:
            a_j, idx_j = heappop(que)
            s.append(idx_j)
            heappush(que, (a_i, idx_i))
            a_j += 1
            if a_j < 0:
                heappush(que, (a_j, idx_j))
        else:
            s.append(idx_i)
            a_i += 1
            if a_i < 0:
                heappush(que, (a_i, idx_i))

cnt = 0
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        cnt += 1
print(cnt)

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

ans = a[0]-1
for i in range(1,t):
  ans -= a[i]
  if ans < 0:
    ans = 0
    break
print(ans)

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

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

Solution (Python):
import sys

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

if len(A) == 1:
    print(A[0] - 1)
else:    
    A.sort(reverse=True)
    other_sum = sum(A[1:])
    print(max(0, A[0] - other_sum - 1))

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

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):
from collections import deque
k,t = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
a = deque(a)
length = len(a)
if length ==1:
    print(sum(a)-1)
    exit()
while length > 1:
    mx = a.pop()
    mn = a.popleft()
    mx -= 1
    mn -= 1
    if mx != 0:
        a.append(mx)
    else:
        length -=1
    if mn != 0:
        a.appendleft(mn)
    else:
        length-=1    
print(max(sum(a)-1,0))

Solution (Python):
k, t = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
double_cnt = 0
total = 0
for i in range(t):
  b = a[i] - double_cnt
  c = total - (double_cnt + 1) + 2
  double_cnt = max(0, b-c)
  total += a[i]
print(double_cnt)

Solution (Python):
def main():
    K, T = map( int, input().split())
    A = list( map( int, input().split()))
    A.sort(reverse=True)
    if A[0] <= (K+1)//2:
        print(0)
    else:
        print((A[0] - (K+1)//2)*2 - (K+1)%2)
if __name__ == '__main__':
    main()

Solution (Python):
K,T = map(int,input().split())
from heapq import heapify, heappop, heappush
A = list(map(int,input().split()))
for i in range(T):
    A[i] = (-A[i],i)
A.append((0,999))
A.sort()
heapify(A)
ans = 0
pre = -1

for i in range(K):
    a,i = heappop(A)
    if pre != i:
        heappush(A,(a+1,i))
        pre = i
    else:
        a2,i2 = heappop(A)
        if a2 < 0:
            pre = i2
            heappush(A,(a2+1,i2))
            heappush(A,(a,i))
        else:
            ans += 1
            heappush(A,(a+1,i))
            heappush(A,(a2,i2))
print(ans)

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

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

a_l = []
for i, a in enumerate(a_l_init):
    a_l.append([a,i])
a_l.sort(reverse=True)

flag = 0
yesterday = -1
for _ in range(k):
    for j in range(t):
        if a_l[j][1] != yesterday:
            a_l[j][0] -= 1
            yesterday = a_l[j][1]
            a_l.sort(reverse=True)
            break
        elif a_l[j+1][0] != 0:
            continue
        else:
            flag = 1
            break
    if flag == 1:
        break

if flag == 0:
    print(0)
else:
    print(a_l[0][0])

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]

def to_bin(x: int) -> str: return format(x, 'b') 
def to_oct(x: int) -> str: return format(x, 'o') 
def to_hex(x: int) -> str: return format(x, 'x') 
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res

from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left


def main():
    k, t = MII()
    aa = MII()
    aa.sort(reverse=True)
    ans = max(aa[0]-1-(k-aa[0]), 0)
    print(ans)



if __name__ == '__main__':
    main()

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


space = A[0] - 1
for x in A[1:]:
    space -= x

print(max(0, space))

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

if suma - maxa >= maxa - 1:
    print(0)
else:
    print(maxa - 1 - (suma-maxa))

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

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

A = list(reversed(sorted(A)))

left_sum = 0
right_sum = 0
for i in A:
    if left_sum < right_sum :
        left_sum += i
    else:
        right_sum += i

if abs(left_sum - right_sum) in [0, 1]:
    print(0)
else:
    a = abs(left_sum - right_sum) - 1
    print(a)

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

table = [False] * (K + 1)

table[0] = True

for n in numbers:
  for i in range(K, 0, -1):
    if i - n >= 0:
      table[i] = table[i] or table[i - n]
    
m = 0

for i, t in enumerate(table):
  if not t:
    continue
  m = i if abs(i - K / 2) < abs(m - K / 2) else m

if abs(2 * m - K) <= 1:
  print(0)
else:
  print(abs(2 * m - K) - 1)

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

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

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



max_a = max(a_input)
print(max(0,max_a-(k-max_a)-1))

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

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

b=a[0]
c=a[1]
for i in range(2,T):
    if b>c:
        c+=a[i]
    else:
        b+=a[i]
if b==c:
    print(0)
    exit()
print(abs(b-c)-1)

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