You are given a sequence $a_1, a_2, \dots, a_n$ consisting of $n$ integers.

You may perform the following operation on this sequence: choose any element and either increase or decrease it by one.

Calculate the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $k$ times.


-----Input-----

The first line contains two integers $n$ and $k$ $(2 \le n \le 10^{5}, 1 \le k \le 10^{14})$ — the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.

The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^{9})$.


-----Output-----

Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $k$ times.


-----Examples-----
Input
4 5
3 1 7 5

Output
2

Input
3 10
100 100 100

Output
0

Input
10 9
4 5 5 7 5 4 5 2 4 3

Output
1



-----Note-----

In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes $[3, 3, 5, 5]$, and the difference between maximum and minimum is $2$. You still can perform one operation after that, but it's useless since you can't make the answer less than $2$.

In the second example all elements are already equal, so you may get $0$ as the answer even without applying any operations.

Difficulty: interview

Starter code:

Solutions:
n, k = map(int, input().split())
a = list(map(int, input().split()))

cnt = {}
for elem in a:
    if elem in cnt:
        cnt[elem] += 1
    else:
        cnt[elem] = 1
cnt = sorted(list(cnt.items()))
for i in range(len(cnt)):
    cnt[i] = list(cnt[i])
left = 0
right = len(cnt) - 1
while k > 0:
    if k < cnt[left][1] and k < cnt[right][1]:
        break
    if left == right:
        break
    if cnt[left][1] <= cnt[right][1]:
        if k >= cnt[left][1] * (cnt[left + 1][0] - cnt[left][0]):
            k -= cnt[left][1] * (cnt[left + 1][0] - cnt[left][0])
            cnt[left + 1][1] += cnt[left][1]
            left += 1
        else:
            cnt[left][0] += k // cnt[left][1]
            k = 0
    else:
        if k >= cnt[right][1] * (cnt[right][0] - cnt[right - 1][0]):
            k -= cnt[right][1] * (cnt[right][0] - cnt[right - 1][0])
            cnt[right - 1][1] += cnt[right][1]
            right -= 1
        else:
            cnt[right][0] -= k // cnt[right][1]
            k = 0
print(cnt[right][0] - cnt[left][0])

def solve(k, a):
    a.sort()
    ans = a[-1] - a[0]
    if ans == 0:
        return 0
    q1 = []
    q2 = []
    for i in range(1, len(a)):
        if a[i] != a[i-1]:
            q1.append([i, a[i] - a[i-1]])
    a = a[::-1]
    for i in range(1, len(a)):
        if a[i] != a[i-1]:
            q2.append([i, a[i-1] - a[i]])
    i1, i2 = 0, 0
    while k >= min(q1[i1][0], q2[i2][0]) and ans > 0:
        if q1[i1][0] <= q2[i2][0]:
            ansd = min(q1[i1][1], k // q1[i1][0])
            ans -= ansd
            k -= ansd * q1[i1][0]
            i1 += 1
        else:
            ansd = min(q2[i2][1], k // q2[i2][0])
            ans -= ansd
            k -= ansd * q2[i2][0]
            i2 += 1
        if max(i1, i2) >= len(q1):
            break
    return max(0, ans)


def main():
    _, k = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    print(solve(k, a))


main()


n, k = list(map(int, input().split()))
a = sorted(map(int, input().split()))
i = 1
while True:
    ans = a[-i] - a[i - 1]
    if (a[i] - a[i - 1]) * i >= k:
        ans -= k // i
        break
    ans = a[-i] - a[i]
    k += a[i - 1] * i
    k -= a[i] * i
    if (a[-i] - a[-i - 1]) * i >= k:
        ans -= k // i
        break
    k += a[-i - 1] * i
    k -= a[-i] * i
    i += 1
    if not ans:
        break
print(ans)


import sys
from collections import Counter
input = sys.stdin.readline

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

S=sorted(set(A))

if len(S)==1:
    print(0)
    return

MIN0=0
MIN1=1
MAX0=-1
MAX1=-2

C=Counter(A)

while k and S[MIN0]!=S[MAX0]:
    
    if C[S[MIN0]]<=C[S[MAX0]] and k>=C[S[MIN0]]:
        
        if k>=(S[MIN1]-S[MIN0])*C[S[MIN0]]:
            
            k-=(S[MIN1]-S[MIN0])*C[S[MIN0]]
            C[S[MIN1]]+=C[S[MIN0]]
            del(C[S[MIN0]])
            MIN0+=1
            MIN1+=1

        else:
            print(S[MAX0]-(S[MIN0]+k//C[S[MIN0]]))
            return

    elif C[S[MAX0]]<=C[S[MIN0]] and k>=C[S[MAX0]]:
        
        if k>=(S[MAX0]-S[MAX1])*C[S[MAX0]]:
            
            k-=(S[MAX0]-S[MAX1])*C[S[MAX0]]
            C[S[MAX1]]+=C[S[MAX0]]
            del(C[S[MAX0]])
            MAX0-=1
            MAX1-=1

        else:
            print((S[MAX0]-k//C[S[MAX0]])-S[MIN0])
            return

    else:
        break

print(S[MAX0]-S[MIN0])



n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

d = {}
for x in a:
    if x not in d:
        d[x] = 0
    d[x] += 1

nums = list(d.keys())
nums.sort()

l = 0
r = len(nums)-1
while l < r:
##    print(l, r, nums, d)
    if d[nums[l]] < d[nums[r]]:
        cur = nums[l]
        nxt = nums[l+1]
        full_cost = (nxt-cur)*d[cur]
        if full_cost <= k:
            d[nxt] += d[cur]
            k -= full_cost
            l+=1
        else:
            mx = k // d[cur]
            nums[l] += mx
            break      
    else:
        cur = nums[r]
        nxt = nums[r-1]
        full_cost = (cur-nxt)*d[cur]
        if full_cost <= k:
            d[nxt] += d[cur]
            k -= full_cost
            r-=1
        else:
            mx = k // d[cur]
            nums[r] -= mx
            break   

print(nums[r]-nums[l])


n, k = list(map(int,input().split()))
seq = list(sorted(map(int,input().split())))

i = 0
j = n-1
result = seq[n-1] - seq[0]

while result > 0:
    if i == j-1:
        used = (seq[i+1]-seq[i])*(i+1)
    else:
        used = (seq[i+1] - seq[i] + seq[j] - seq[j-1])*(i+1)
    if used >= k:
        result -= k//(i+1)
        break
    k -= used
    if i == j-1:
        result = 0
        break
    result = seq[j-1]-seq[i+1]
    i += 1
    j -= 1

print(result)


n, k = map(int, input().split(' '))

arr = list(map(int, input().split(' ')))

arr.sort()

dif = [0] * n

for i in range(n - 1):
  dif[i] = arr[i + 1] - arr[i]

i = 0
j = n - 2
left = 1
right = 1

last = -1

while(k > 0 and i <= j):
  if(dif[i]) == 0:
    left += 1
    i += 1
    continue
  if(dif[j]) == 0:
    right += 1
    j -= 1
    continue

  if(i == j):
    last = i

  if(left <= right):
    difToSubstract = min(dif[i], k // left)

    if(difToSubstract == 0):
      k = 0
      break

    k -= left * difToSubstract
    dif[i] -= difToSubstract
  else:
    difToSubstract = min(dif[j], k // right)

    if(difToSubstract == 0):
      k = 0
      break

    k -= right * difToSubstract
    dif[j] -= difToSubstract
      
if(i <= j):
  sol = 0

  for u in range(i, j + 1):
    sol += dif[u]

  print(sol)

else:
  print(dif[last])

n,k=list(map(int,input().split()))
li=list(map(int,input().split()))
d={}
l=[]
for i in li:
    try:
        d[i]+=1
    except KeyError:
        d[i]=1
        l.append(i)
l.sort()
z=1
a=0
b=len(l)-1
while k>0:
    if a==b:
        z=0
        break
    if d[l[a]]>d[l[b]]:
        s=d[l[b]]*(l[b]-l[b-1])
        if s<=k:
            k-=s
            d[l[b-1]]+=d[l[b]]
            b-=1
        else:
            b1=k//d[l[b]]
            z=2
            break
    else:
        s=d[l[a]]*(l[a+1]-l[a])
        if s<=k:
            k-=s
            d[l[a+1]]+=d[l[a]]
            a+=1
        else:
            a1=k//d[l[a]]
            z=3
            break
        
if z==0:
    print(0)
elif z==1:
    print(l[b]-l[a])
elif z==2:
    print(l[b]-l[a]-b1)
else:
    print(l[b]-l[a]-a1)



n, k = [int(i) for i in input().split(' ')]
a = sorted([int(i) for i in input().split(' ')])

if n == 1:
    print(0)
    return
tot = 0
i, j = 1, n-2

while j - i>=-1:
    do = i>(n-j-1)

    last = tot
    tot += i*(a[i]-a[i-1]) if not do else (n - j - 1)*(a[j+1] - a[j])

    if tot >= k:

        if do:
            a[-1] -= (k - last)//(n-j-1)
        else:
            a[0] += (k - last)//i
        break
    
    if do:
        a[-1] = a[j]
        j-=1
    else:
        a[0] = a[i]
        i+=1

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

'''
    Author : thekushalghosh
    Team   : CodeDiggers
'''
import sys,math
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
i = 1
while i > 0:
    q = a[-i] - a[i - 1]
    if (a[i] - a[i - 1]) * i >= k:
        q = q - (k // i)
        break
    k = k + (a[i - 1] * i) - (a[i] * i)
    q = a[-i] - a[i]
    if (a[-i] - a[-i - 1]) * i >= k:
        q = q - (k // i)
        break
    k = k + (a[-i - 1] * i) - (a[-i] * i)
    i = i + 1
    if not q:
        break
print(q)

from collections import deque
n, k = list(map(int, input().split()))
li = list(map(int, input().split()))
li.sort()
# print(li)
dq = deque()

a = li[0]
countt = 1
distp = -1
for i in range(1, len(li)):
    if li[i] == a:
        countt += 1
    else:
        dq.append([a, countt, distp, li[i]-a])
        distp = li[i]-a
        countt = 1

    a = li[i]

dq.append([a, countt, distp, -1])
diff = li[-1]-li[0]

while k > 0 and diff > 0:
    if dq[0][1] > dq[-1][1]:  # go from top
        if k > dq[-1][2] * dq[-1][1]:
            k -= dq[-1][2] * dq[-1][1]
            x1 = dq.pop()
            x2 = dq.pop()
            dq.append([x2[0], x2[1]+x1[1], x2[2], -1])
            diff -= x1[0]-x2[0]
        else:
            diff -= k // dq[-1][1]
            k = 0
    else: # go from bot
        if k > dq[0][3] * dq[0][1]:
            k -= dq[0][3] * dq[0][1]
            x1 = dq.popleft()
            x2 = dq.popleft()
            dq.appendleft([x2[0], x2[1]+x1[1], -1, x2[3]])
            diff -= x2[0]-x1[0]
        else:
            diff -= k // dq[0][1]
            k = 0
            # print("yyyyy")
    
    # print(dq)
    # print(f"diff:{diff} k:{k}")
print(diff)


n,k=map(int,input().split())
a=input().split()
for i in range(n):
    a[i]=int(a[i])
a.sort()
b=[]
count=0
for i in range(n):
    if(i==0):
        count+=1
        if(i==n-1):
            b.append([a[i],count])
    else:
        if(a[i]==a[i-1]):
            count+=1
            if(i==n-1):
                b.append([a[i],count])
        else:
            b.append([a[i-1],count])
            count=1
            if(i==n-1):
                b.append([a[i],count])
while k:
    if(len(b)==1):break
    if(b[0][1]<b[len(b)-1][1]):
        if(k>=(b[1][0]-b[0][0])*b[0][1]):
            b[1][1]+=b[0][1]
            k-=(b[1][0]-b[0][0])*b[0][1]
            b.pop(0)
        else:
            b[0][0]+=k//b[0][1]
            k=0
    else:
        if(k>=(b[len(b)-1][0]-b[len(b)-2][0])*b[len(b)-1][1]):
            b[len(b)-2][1]+=b[len(b)-1][1]
            k-=(b[len(b)-1][0]-b[len(b)-2][0])*b[len(b)-1][1]
            b.pop(len(b)-1)
        else:
            b[len(b)-1][0]-=k//b[len(b)-1][1]
            k=0
print(b[len(b)-1][0]-b[0][0])            

from collections import defaultdict
from itertools import accumulate
from bisect import bisect_left

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
d = defaultdict(int)

for u in a:
	d[u] += 1

c = sorted(d.keys())

cnt = [d[i] for i in c]
snt = [i * d[i] for i in c]

pc = list(accumulate(cnt))
sc = list(accumulate(cnt[::-1]))[::-1]

ps = list(accumulate(snt))
ss = list(accumulate(snt[::-1]))[::-1]

def get_high(rest):
	l, r = c[0] - 1, c[-1]
	while r - l > 1:
		mid = (l + r) // 2 + (l + r) % 2
		i = bisect_left(c, mid)
		if ss[i] - mid * sc[i] <= rest:
			r = mid
		else:
			l = mid
	return r

def calc_ans(low):
	if low < c[0]:
		return 10 ** 100
	i = bisect_left(c, low)
	if c[i] != low:
		i -= 1
	if low * pc[i] - ps[i] > k:
		return 10 ** 100
	rest = k - (low * pc[i] - ps[i])
	high = get_high(rest)
	return max(high - low, 0)

l, r = c[0], c[-1]

while r - l > 1:
	mid = (l + r) // 2
	mm = (mid + r) // 2
	if calc_ans(mid) <= calc_ans(mm):
		r = mm
	else:
		l = mid

print(min(calc_ans(l), calc_ans(r)))


n,k=list(map(int,input().split()))
l1=list(map(int,input().split()))
l1.sort()
i=0
j=n-1
left=1
right=1
while i<j and k>0:
    x=l1[i+1]-l1[i]
    y=l1[j]-l1[j-1]
    if left==right:
        if k>=left*x:
            k-=left*x
            i+=1
            left+=1
        else :
            l1[i]+=(k)//left
            break
    else :
        if k>=right*y:
            k-=right*y
            j-=1
            right+=1
        else :
            l1[j]-=(k)//right
            break

print(l1[j]-l1[i])


n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
l.sort()
s = 0
for i in range(n):
	s += abs(l[i]-l[n//2])
if s <= k:
	print(0)
else:
	i = 0
	while True:
		if i == n - 1:
			break
		if l[i + 1] != l[i]:
			break
		i += 1
	p = i
	left = p + 1
	i = n - 1
	#print(l)################
	while True:
		if i == 0:
			break
		if l[i - 1] != l[i]:
			break
		i -= 1
	kon = i
	right = n - kon
	while True:#right <= k or left <= k:
		#print(p, kon, left, right, k)###############
		if left <= right:
			if k >= left*(l[p+1]-l[p]):
				k -= left*(l[p+1]-l[p])
				while True:
					p += 1
					left += 1
					if p >= n:
						break
					if l[p+1] != l[p]:
						break
			else:
				print(l[kon]-l[p]-k//left)
				break
		else:
			if k >= right*(l[kon]-l[kon-1]):
				k -= right*(l[kon]-l[kon-1])
				while True:
					kon -= 1
					right += 1
					if kon == 0:
						break
					if l[kon] != l[kon-1]:
						break
			else:
				print(l[kon]-l[p]-k//right)
				break			


# encoding: utf-8
from sys import stdin

n, k = [int(i) for i in stdin.readline().strip().split()]
a = [int(i) for i in stdin.readline().strip().split()]
a.sort()

ups = n * [0]
downs = n * [0]

for i in range(0, n - 1):
    ups[i + 1] = ups[i] + (i + 1) * (a[i + 1] - a[i])

for i in range(n - 1, 0, -1):
    downs[i - 1] = downs[i] + (n - i) * (a[i] - a[i - 1])


def find_max(steps):
    """Lowest possible maximum reachable for given number of steps"""
    l, r = 0, n - 1
    x = None
    while l <= r:
        m = (l + r) // 2
        if downs[m] <= steps:
            x = m
            # downs[l:m] contains bigger values
            r = m - 1
        else:
            l = m + 1

    value = a[x]
    if x > 0 and downs[x] < steps:
        value -= (steps - downs[x]) // (n - x)

    return value


def find_min(steps):
    l, r = 0, n - 1
    x = None
    while l <= r:
        m = (l + r) // 2
        if ups[m] <= steps:
            # ups[m:r] contains bigger values
            x = m
            l = m + 1
        else:
            r = m - 1

    value = a[x]
    if x < n:
        value += (steps - ups[x]) // (x + 1)

    return value


best_diff = a[-1] - a[0]
for i in range(n):
    if ups[i] > k:
        break
    min_a = a[i]
    max_a = find_max(k - ups[i])
    if max_a <= min_a:
        best_diff = 0
        break
    best_diff = min(best_diff, max_a - min_a)

for i in range(n - 1, -1, -1):
    if best_diff == 0:
        break
    if downs[i] > k:
        break
    max_a = a[i]
    min_a = find_min(k - downs[i])
    if min_a >= max_a:
        best_diff = 0
        break
    best_diff = min(best_diff, max_a - min_a)

print(best_diff)


import sys
n, k = list(map(int, input().split()))
num = [int(x) for x in input().split()]
num.sort()
if (n == 1):
    print(0)
    return
pre = 0
pree = num[0]
lat = n - 1
latt = num[n - 1]
pren = 1
latn = 1

while (k > 0):
    while (num[pre + 1] == pree and pre + 1 < lat):
        pre += 1
        pren += 1
    while (num[lat - 1] == latt and pre < lat - 1):
        lat -= 1
        latn += 1
    if (pren > k and latn > k): 
        break;
    if (pree < latt):
        if (pren < latn):
            if (pren * (num[pre + 1] - num[pre]) <= k):
                k -= pren * (num[pre + 1] - num[pre])
                pre += 1
                pren += 1
                pree = num[pre]
            else: 
                pree += k // pren
                k %= pren
        else:
            if (latn * (num[lat] - num[lat - 1]) <= k):
                k -= latn * (num[lat] - num[lat - 1])
                lat -= 1
                latn += 1
                latt = num[lat]
            else:
                latt -= k // latn
                k %= latn
    else:
        break;
    
print(latt-pree)



# encoding: utf-8
from sys import stdin

n, k = [int(i) for i in stdin.readline().strip().split()]
a = [int(i) for i in stdin.readline().strip().split()]
a.sort()

i = 0
j = n - 1
a_min = a[i]
a_max = a[j]
while i < j:
    if a[i] == a[i + 1]:
        i += 1
        a_min = a[i]
    elif a[j] == a[j - 1]:
        j -= 1
        a_max = a[j]
    else:
        if i + 1 <= n - j:
            required_steps = (a[i + 1] - a[i]) * (i + 1)
            if required_steps > k:
                a_min += k // (i + 1)
                break
            else:
                i += 1
                k -= required_steps
                a_min = a[i]
        else:
            required_steps = (a[j] - a[j - 1]) * (n - j)
            if required_steps > k:
                a_max -= k // (n - j)
                break
            else:
                j -= 1
                k -= required_steps
                a_max = a[j]

print(a_max - a_min)


# encoding: utf-8
from sys import stdin

n, k = [int(i) for i in stdin.readline().strip().split()]
a = [int(i) for i in stdin.readline().strip().split()]
a.sort()

i = 0
j = n - 1
a_min = a[i]
a_max = a[j]
while i < j:
    if i + 1 <= n - j:
        required_steps = (a[i + 1] - a[i]) * (i + 1)
        if required_steps > k:
            a_min += k // (i + 1)
            break
        else:
            i += 1
            k -= required_steps
            a_min = a[i]
    else:
        required_steps = (a[j] - a[j - 1]) * (n - j)
        if required_steps > k:
            a_max -= k // (n - j)
            break
        else:
            j -= 1
            k -= required_steps
            a_max = a[j]

print(a_max - a_min)


# Never give up. You only get one life and a year. Go for it!
import sys
import math




n,k=list(map(int,input().split()))
A=[int(i) for i in input().split()]

A.sort()

l=0
r=n-1

while(l<r and k):
    temp=((A[l+1]-A[l])*(l+1)+(A[r]-A[r-1])*(n-r))
    if(k>=temp):
        k-=temp
        l+=1
        r-=1

    else:
        ans=A[r]-A[l]-(k//(l+1))
        print(ans)
        return




print(0)



n,k=map(int,input().strip().split())
a =list(map(int,input().strip().split()))
from collections import deque, Counter
temp = Counter(a)
a = deque(sorted(map(lambda x: [x,temp[x]], temp)))
# print(a)
while( (k>=a[0][1] or k>=a[-1][1] ) and len(a)>1):
    # forward
    cf,f,smf = a[0][1], a[0][0], a[1][0]
    cr,r,smr = a[-1][1], a[-1][0], a[-2][0]

    if(cf < cr):
        # front should be removed
        temp = cf*(smf-f)
        if(temp<=k):
            k-=temp
            a.popleft()
            a[0][1]+=cf
        else:
            factor=k//cf
            temp1 = factor*cf
            k-=temp1
            a[0][0]=f+factor




    else:
        # back should be removed
        temp = cr*(r-smr)
        if(temp<=k):
            k-=temp
            a.pop()
            a[-1][1]+=cr
        else:
            factor=k//cr
            temp1 = factor*cr
            k-=temp1
            a[-1][0]=r-factor


print(max(a)[0]-min(a)[0])

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
left = 1
right = 1
while 1:
    if left*(a[left]-a[left-1]) <= k:
        k -= left*(a[left]-a[left-1])
        left += 1
    else:
        print(a[n-right]-a[left-1]-int(k/left))
        return
    if left+right > n:
        print(0)
        return
    if right*(a[n-right]-a[n-1-right]) <= k:
        k -= right*(a[n-right]-a[n-1-right])
        right += 1
    else:
        print(a[n-right]-a[left-1]-int(k/right))
        return
    if left+right > n:
        print(0)
        return


import atexit
import io
import sys

_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER


@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
left = 1
right = 1
while 1:
    if left*(a[left]-a[left-1]) <= k:
        k -= left*(a[left]-a[left-1])
        left += 1
    else:
        print(a[n-right]-a[left-1]-int(k/left))
        return
    if left+right > n:
        print(0)
        return
    if right*(a[n-right]-a[n-1-right]) <= k:
        k -= right*(a[n-right]-a[n-1-right])
        right += 1
    else:
        print(a[n-right]-a[left-1]-int(k/right))
        return
    if left+right > n:
        print(0)
        return


'''
Fuad Ashraful Mehmet
Bsc in CSE
University of Asia Pacific
Dhaka,Bangladesh

problem:from code forces


'''
# install xampp https://vitux.com/how-to-install-xampp-on-your-ubuntu-18-04-lts-system/




class Solve():
    
    def __init__(self):
        self.n,self.k=map(int,input().split())
        self.fuad=list(map(int,input().split()))
        self.fuad.sort()
    def FuckCase(self):
        
        for i in range(int(self.n/2)):
            
            s=(self.fuad[i+1]-self.fuad[i])*(i+1)+(self.fuad[self.n-i-1]-self.fuad[self.n-i-2])*(i+1)

            # print("i {} j {} s {} k {}".format(i,self.n-i-1,s,self.k))
            if s<=self.k:
                self.k-=s
            else:
                print(self.fuad[self.n-i-1]-self.fuad[i]-int((self.k/(i+1))))
                return


        print("0")



obj =Solve()

obj.FuckCase()