Untitled

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5, maxadad = 1e9;
long long n, k, arr[maxn], psaval[maxn], psakhar[maxn];

int bs_bishtar(int adad, int l, int r){
	int mid;
	while(l + 1 < r){
		mid = (r + l) / 2;
		if(arr[mid] <= adad){
			l = mid;
		}
		else{
			r = mid;
		}
	}
	return r;
}

int bs_kamtar(int adad, int l, int r){
	int mid;
	while(l + 1 < r){
		mid = (r + l) / 2;
		if(arr[mid] < adad){
			l = mid;
		}
		else{
			r = mid;
		}
	}
	return l;
}

long long op_count(int l, int r){
	int ind_kam = bs_kamtar(l, -1, n);
	int ind_bish = bs_bishtar(r, -1, n);
	long long opkam = 0, opbish = 0;
	if(ind_kam != -1){
		opkam = 1ll * l * (ind_kam + 1) - psaval[ind_kam];
	}
	if(ind_bish != n){
		opbish = 1ll * psakhar[ind_bish] - r * (n - ind_bish);
	}
	
	return opkam + opbish;
}

int bs_dareh(int bazeh, int l, int r){
	int mid1, mid2;
	long long op1, op2;
	while(l + 1 < r){
		mid1 = (l + r) / 2;
		mid2 = mid1 + 1;
		op1 = op_count(mid1, mid1 + bazeh);
		op2 = op_count(mid2, mid2 + bazeh);
		
		if(op1 < op2){
			r = mid1;
		}
		else{
			l = mid2;
		}
	}
	
	op1 = op_count(l, l + bazeh);
	op2 = op_count(r, r + bazeh);
	
	if(op1 > op2){
		return r;
	}
	return l;
}

bool bs_bazeh_check(int bazeh){
	int l = bs_dareh(bazeh, 1, maxadad - bazeh);
	int r = l + bazeh;
	long long op = op_count(l, r);
	if(op <= k){
		return 1;
	}
	return 0;
}

int bs_bazeh(int l, int r){
	int mid;
	while(l + 1 < r){
		mid = (l + r) / 2;
		if(!bs_bazeh_check(mid)){
			l = mid;
		}
		else{
			r = mid;
		}
	}
	return r;
}

int main(){
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}	
	sort(arr, arr + n);
	for(int i = 0; i < n; i++){
		psaval[i] = arr[i];
		if(i){
			psaval[i] += psaval[i - 1];
		}
	}
	for(int i = n - 1; i >= 0; i--){
		psakhar[i] = arr[i];
		if(i < n - 1){
			psakhar[i] += psakhar[i + 1];
		}
	}
	
	cout << bs_bazeh(-1, maxadad);
}