There are N piles of coins each containing  Ai (1<=i<=N) coins. Find the minimum number of coins to be removed such that the absolute difference of coins in any two piles is at most K.
Note: You can also remove a pile by removing all the coins of that pile.
Example 1:
Input:
N = 4, K = 0
arr[] = {2, 2, 2, 2}
Output:
0
Explanation:
For any two piles the difference in the
number of coins is <=0. So no need to
remove any coins. 
Example 2:
Input:
N = 6, K = 3
arr[] = {1, 5, 1, 2, 5, 1} 
Output :
2
Explanation:
If we remove one coin each from both
the piles containing 5 coins , then
for any two piles the absolute difference
in the number of coins is <=3. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minSteps() which takes 2 integers N, and K and an array A of size N as input and returns the minimum number of coins that need to be removed.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ K ≤ 10^{4}
1 ≤ A[i] ≤ 103

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def minSteps(self, A, N, K):

        # code here 

Solutions:
from collections import Counter

class Solution:

	def minSteps(self, A, N, K):
		C = Counter(A)
		A = [[v, cnt] for (v, cnt) in C.items()]
		A.sort(key=lambda p: p[0])
		N = len(A)
		for i in range(N - 1, -1, -1):
			if A[i][0] - A[0][0] <= K:
				break
		i += 1
		if i >= N:
			return 0
		(allcnt, cost) = (0, 0)
		for j in range(i, N):
			allcnt += A[j][1]
			cost += (A[j][0] - A[0][0] - K) * A[j][1]
		ans = cost
		for j in range(N - 1):
			if A[N - 1][0] - A[j][0] <= K:
				break
			v = A[j][0]
			cost += v * A[j][1]
			vn = A[j + 1][0]
			diff = vn - v
			while i < N:
				if A[i][0] - vn <= K:
					cost -= (A[i][0] - v - K) * A[i][1]
					allcnt -= A[i][1]
					i += 1
				else:
					cost -= diff * allcnt
					break
			ans = min(ans, cost)
		return ans


def upper_bound(A, L, R, K):
	pos = R + 1
	while L <= R:
		M = (L + R) // 2
		if A[M] > K:
			pos = M
			R = M - 1
		else:
			L = M + 1
	return pos

class Solution:

	def minSteps(self, a, N, K):
		p = [0] * N
		a.sort()
		p[0] = a[0]
		for i in range(1, N):
			p[i] = p[i - 1] + a[i]
		ans = (1 << 31) - 1
		prev = 0
		for i in range(N):
			pos = upper_bound(a, i, N - 1, a[i] + K)
			if i > 0 and a[i] != a[i - 1]:
				prev = p[i - 1]
			ans = min(ans, prev + p[N - 1] - p[pos - 1] - (N - pos) * (a[i] + K))
		return ans


class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		presum = A.copy()
		for i in range(1, N):
			presum[i] += presum[i - 1]
		res = sum(A)
		upto = 0

		def findpos(L, R, diff):
			pos = R + 1
			while L <= R:
				mid = (L + R) // 2
				if A[mid] > diff:
					pos = mid
					R = mid - 1
				else:
					L = mid + 1
			return pos
		for i in range(N):
			pos = findpos(i, N - 1, A[i] + K)
			if i > 0 and A[i] != A[i - 1]:
				upto = presum[i - 1]
			res = min(res, upto + presum[N - 1] - presum[pos - 1] - (N - pos) * (A[i] + K))
		return res


import bisect

class Solution:

	def minSteps(self, A, N, K):
		start = 0
		end = N - 1
		s = sum(A)
		A.sort()
		cnt = 0
		csum = []
		for i in range(N):
			csum.append(A[i] if i == 0 else csum[i - 1] + A[i])
		ans = csum[N - 1]
		safe_till = 0
		extras = 0
		on_left_cant_exist_so_remove = 0
		for i in range(N):
			if i != 0 and A[i] == A[i - 1]:
				safe_till += A[i]
				continue
			index = bisect.bisect_right(A, A[i] + K)
			if index > N:
				index = N - 1
			temp = s - csum[index - 1]
			temp = temp - (A[i] + K) * (N - index)
			ans = min(ans, safe_till + temp)
			safe_till += A[i]
		return ans


import bisect

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pre = 0
		s = sum(A)
		pre_s = []
		for i in A:
			if len(pre_s) == 0:
				pre_s.append(i)
			else:
				pre_s.append(i + pre_s[-1])
		coins = float('inf')
		for i in range(len(A)):
			if i != 0 and A[i] == A[i - 1]:
				pre += A[i]
				continue
			index = bisect.bisect_right(A, A[i] + K)
			if index > N:
				index = N
			temp = s - pre_s[index - 1]
			temp = temp - (A[i] + K) * (N - index)
			coins = min(coins, pre + temp)
			pre += A[i]
		return coins


class Solution:

	def binarysearch(self, arr, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			if arr[mid] > k:
				return self.binarysearch(arr, l, mid - 1, k)
			else:
				return self.binarysearch(arr, mid + 1, r, k)
		return l

	def minSteps(self, A, N, K):
		A.sort()
		presum = [0] * N
		presum[0] = A[0]
		for i in range(1, N):
			presum[i] = presum[i - 1] + A[i]
		l = self.binarysearch(A, 0, N - 1, A[0] + K)
		m1 = presum[-1] - presum[l - 1] - (N - l) * (A[0] + K)
		m2 = 100000000
		for i in range(1, N):
			l = self.binarysearch(A, 0, N - 1, A[i] + K)
			m2 = presum[i - 1] + (presum[-1] - presum[l - 1]) - (N - l) * (A[i] + K)
			m1 = min(m1, m2)
		return m1


from bisect import bisect_right

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		cs = [0] * N
		cs[0] = A[0]
		for i in range(1, N):
			cs[i] = cs[i - 1] + A[i]
		ans = 2 ** 31 - 1
		for i in range(N):
			ub = bisect_right(A, A[i] + K)
			curr = 0
			if i > 0:
				curr += cs[i - 1]
			if ub < N:
				curr += cs[-1] - cs[ub - 1] - (N - ub) * (K + A[i])
			ans = min(ans, curr)
		return ans


from bisect import bisect_left

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		p_sum = []
		p_sum.append(A[0])
		for i in range(1, N):
			p_sum.append(p_sum[-1] + A[i])
		s = 0
		res = 1000000000.0
		for i in range(N):
			toFind = A[i] + K
			x = bisect_left(A, toFind)
			if x > 0 and x < N:
				toRemove = p_sum[N - 1] - p_sum[x - 1]
				toReduce = (N - x) * toFind
				toRemove -= toReduce
				res = min(res, toRemove + s)
			s += A[i]
		return res if res != 1000000000.0 else 0


from bisect import bisect_right

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pre = [A[0]]
		for i in range(1, N):
			pre.append(pre[i - 1] + A[i])
		res = float('inf')
		prev = 0
		for (i, n) in enumerate(A):
			ind = bisect_right(A, n + K)
			if i > 0 and A[i] != A[i - 1]:
				prev = pre[i - 1]
			res = min(res, prev + pre[N - 1] - pre[ind - 1] - (N - ind) * (n + K))
		return res


class Solution:

	def binarySearch(self, A, N, ele):
		start = 0
		end = N - 1
		res = -1
		while start <= end:
			mid = (start + end) // 2
			if A[mid] > ele:
				res = mid
				end = mid - 1
			else:
				start = mid + 1
		return res

	def minSteps(self, A, N, K):
		A.sort()
		ans = 10000000000.0
		prev = 0
		prefix = []
		for i in range(N):
			if i == 0:
				prefix.append(A[0])
			else:
				prefix.append(prefix[i - 1] + A[i])
		for i in range(N):
			index = self.binarySearch(A, N, A[i] + K)
			if i > 0:
				prev = prefix[i - 1]
			if index < 0:
				ans = min(ans, prev)
			else:
				ans = min(ans, prev + (prefix[-1] - prefix[index - 1] - (N - index) * (A[i] + K)))
		return ans


import bisect as bt

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pf = [0] * N
		pf[0] = A[0]
		for i in range(1, N):
			pf[i] = pf[i - 1] + A[i]
		res = float('inf')
		for i in range(N):
			if i != 0:
				temp = pf[i - 1]
			else:
				temp = 0
			if abs(A[i] - A[-1]) > K:
				mx = A[i] + K + 1
				ix = bt.bisect_left(A, mx, i + 1, N)
				if ix < N:
					temp += pf[-1] - pf[ix - 1] - (N - ix) * (mx - 1)
			res = min(res, temp)
			if abs(A[i] - A[-1]) <= K:
				break
		return res


from bisect import bisect_right

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		prefixArr = []
		prefixArr.append(A[0])
		for i in range(1, N):
			prefixArr.append(prefixArr[i - 1] + A[i])
		ans = 1000000000.0
		prev = 0
		for i in range(N):
			perm = A[i] + K
			ind = bisect_right(A, perm)
			actualSum = prefixArr[N - 1] - prefixArr[ind - 1]
			red = perm * (N - ind)
			actualSum -= red
			ans = min(ans, actualSum + prev)
			prev += A[i]
		return ans


from bisect import bisect_right

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		p = [A[0]]
		for i in range(1, N):
			p.append(p[-1] + A[i])
		j = bisect_right(A, A[0] + K)
		ans = p[-1] - p[j - 1] - (A[0] + K) * (N - j)
		for i in range(1, N):
			j = bisect_right(A, A[i] + K)
			if A[i] != A[i - 1]:
				ans = min(ans, p[i - 1] + (p[-1] - p[j - 1]) - (A[i] + K) * (N - j))
		return ans


def ub(A, l, r, key):
	ans = r + 1
	while l <= r:
		mid = l + (r - l >> 1)
		if A[mid] > key:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	return ans

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		ans = 1000000000.0
		pref = [0] * N
		pref[0] = A[0]
		for i in range(1, N):
			pref[i] = pref[i - 1] + A[i]
		prev = 0
		for i in range(N):
			key = A[i] + K
			ix = ub(A, i, N - 1, key)
			if i > 0 and A[i] != A[i - 1]:
				prev = pref[i - 1]
			ans = min(ans, prev + (pref[N - 1] - pref[ix - 1]) - key * (N - ix))
		return ans


from heapq import heappush, heappop
import math

class Solution:

	def minSteps(self, A, n, k):
		arr = [0 for i in range(n)]
		A.sort()
		l = len(A)
		cnt = 0
		heap = [-1 * A[l - 1]]
		for i in range(l - 2, -1, -1):
			temp = 0
			arr[i] = cnt * (A[i + 1] - A[i]) + arr[i + 1]
			while heap and -1 * heap[0] > A[i] + k:
				temp += -1 * heap[0] - (A[i] + k)
				heappop(heap)
				cnt += 1
			arr[i] += temp
			heappush(heap, -1 * A[i])
		ans = math.inf
		pre = [A[0]]
		for i in range(1, n):
			pre.append(pre[i - 1] + A[i])
		for i in range(n):
			if i == 0:
				ans = min(ans, arr[i])
			else:
				ans = min(ans, pre[i - 1] + arr[i])
		return ans


import bisect

class Solution:

	def minSteps(self, arr, n, k):
		arr.sort()
		coins_to_remove = (arr[-1] - arr[0]) * n
		cum_sum_array = [0 for _ in range(n)]
		cum_sum_array[0] = arr[0]
		for i in range(1, n):
			cum_sum_array[i] = cum_sum_array[i - 1] + arr[i]
		start = 0
		for i in range(n):
			trim_point_idx = bisect.bisect(arr, arr[i] + k, hi=n, lo=i)
			if i > 0 and arr[i] != arr[i - 1]:
				start = cum_sum_array[i - 1]
			coins_to_remove_after_trim_point = cum_sum_array[n - 1] - cum_sum_array[trim_point_idx - 1] - (n - trim_point_idx) * (arr[i] + k)
			coins_to_remove = min(coins_to_remove, start + coins_to_remove_after_trim_point)
		return coins_to_remove


from collections import Counter

class Solution:

	def minSteps(self, A, N, K):
		dp = {}
		C = Counter(A)
		A = [[v, cnt] for (v, cnt) in C.items()]
		A.sort(key=lambda p: p[0])
		N = len(A)
		for i in range(N - 1, -1, -1):
			if A[i][0] - A[0][0] <= K:
				break
		i += 1
		if i >= N:
			return 0
		(allcnt, cost) = (0, 0)
		for j in range(i, N):
			allcnt += A[j][1]
			cost += (A[j][0] - A[0][0] - K) * A[j][1]
		ans = cost
		for j in range(N - 1):
			if A[N - 1][0] - A[j][0] <= K:
				break
			v = A[j][0]
			cost += v * A[j][1]
			vn = A[j + 1][0]
			diff = vn - v
			while i < N:
				if A[i][0] - vn <= K:
					cost -= (A[i][0] - v - K) * A[i][1]
					allcnt -= A[i][1]
					i += 1
				else:
					cost -= diff * allcnt
					break
			ans = min(ans, cost)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.minSteps(A, N, K))


import sys

class Solution:

	def findindex(self, low, high, minm, arr):
		res = -1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] > minm:
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res

	def minSteps(self, arr, n, k):
		arr.sort()
		prefix_sum = [0] * n
		prefix_sum[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			prefix_sum[i] = arr[i] + prefix_sum[i + 1]
		sum1 = 0
		ans = sys.maxsize
		for i in range(n):
			minm = arr[i] + k
			index = self.findindex(i, n - 1, minm, arr)
			if index == -1:
				ans = min(ans, sum1)
				continue
			currsum = prefix_sum[index] - (n - index) * (arr[i] + k)
			currsum += sum1
			ans = min(ans, currsum)
			sum1 += arr[i]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.minSteps(A, N, K))


class Solution:

	def minSteps(self, a, n, k):
		from bisect import bisect_right
		a.sort()
		prefixsum = [0] * n
		prefixsum[0] = a[0]
		for i in range(1, n):
			prefixsum[i] = prefixsum[i - 1] + a[i]
		ans = 2 ** 32
		for i in range(n):
			if i == 0:
				ind = bisect_right(a, a[i] + k)
				t = n - ind
				right = prefixsum[-1] - prefixsum[ind - 1]
				cur_ans = right - t * (a[i] + k)
				ans = min(ans, cur_ans)
			elif i == n - 1:
				left = prefixsum[i - 1]
				ans = min(ans, left)
			else:
				left = prefixsum[i - 1]
				ind = bisect_right(a, a[i] + k)
				t = n - ind
				right = prefixsum[-1] - prefixsum[ind - 1]
				cur_ans = left + (right - t * (a[i] + k))
				ans = min(ans, cur_ans)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.minSteps(A, N, K))


from itertools import accumulate
from bisect import bisect_left

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pre = [0] + list(accumulate(A))
		cost = float('inf')
		for i in range(N):
			discard = pre[i]
			max_reach = bisect_left(A, A[i] + K, i + 1, N)
			trim = pre[-1] - pre[max_reach] - (A[i] + K) * (N - max_reach)
			cost = min(cost, discard + trim)
		return cost
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.minSteps(A, N, K))


from bisect import bisect_right

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		p = [A[0]]
		for i in range(1, N):
			p.append(p[-1] + A[i])
		j = bisect_right(A, A[0] + K)
		ans = p[-1] - p[j - 1] - (A[0] + K) * (N - j)
		for i in range(1, N):
			j = bisect_right(A, A[i] + K)
			ans = min(ans, p[i - 1] + (p[-1] - p[j - 1]) - (A[i] + K) * (N - j))
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.minSteps(A, N, K))


import sys

class Solution:

	def minSteps(self, a, n, k):
		cnt = 0
		self.arr = sorted(a)
		pre_sum = []
		for ele in self.arr:
			if not pre_sum:
				curr = 0
			else:
				curr = pre_sum[-1]
			pre_sum.append(curr + ele)
		ans = sys.maxsize
		for (i, ele) in enumerate(self.arr):
			if i == 0:
				drop_coins = 0
			else:
				drop_coins = pre_sum[i - 1]
			mn = ele
			index = self.get_index(mn + k)
			if index != -1:
				tot = pre_sum[-1] - pre_sum[index - 1]
				expected = (mn + k) * (n - index)
				drop_coins += tot - expected
			ans = min(ans, drop_coins)
		return ans

	def get_index(self, key):
		l = 0
		u = len(self.arr) - 1
		while l < u:
			mid = (l + u) // 2
			if self.arr[mid] <= key:
				l = mid + 1
			else:
				u = mid
		if self.arr[u] <= key:
			return -1
		return u
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.minSteps(A, N, K))


class Solution:

	def minSteps(self, a, n, k):

		def upper_bound(low, high, target):
			ans = high + 1
			while low <= high:
				mid = low + high >> 1
				if a[mid] > target:
					ans = mid
					high = mid - 1
				else:
					low = mid + 1
			return ans
		a.sort()
		pre = [0] * (n + 1)
		pre[0] = a[0]
		for i in range(1, n):
			pre[i] = pre[i - 1] + a[i]
		ans = float('inf')
		for i in range(n):
			idx = upper_bound(i, n - 1, a[i] + k)
			ans = min(ans, pre[i - 1] + (pre[n - 1] - pre[idx - 1]) - (n - idx) * (a[i] + k))
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ob = Solution()
		print(ob.minSteps(A, N, K))


from bisect import *

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pre = [0] * (N + 1)
		pre[0] = A[0]
		suf = [0] * (N + 1)
		for i in range(N - 1, -1, -1):
			suf[i] = suf[i + 1] + A[i]
		for i in range(1, N):
			pre[i] = pre[i - 1] + A[i]
		ans = 10 ** 9
		for i in range(N):
			temp = 0
			ind = bisect_right(A, A[i] + K)
			temp += pre[i - 1]
			temp += suf[ind]
			temp -= (N - ind) * (A[i] + K)
			ans = min(ans, temp)
		return ans


class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		ps = [0]

		def bs(l, r, target):
			while l < r:
				m = (l + r) // 2
				if A[m] >= target:
					r = m
				else:
					l = m + 1
			return l
		for i in range(N):
			ps.append(A[i] + ps[-1])
		answer = float('inf')
		for i in range(N):
			small = A[i]
			remove_all = ps[i]
			idx = bs(i, N - 1, small + K + 1)
			if A[idx] < small + K + 1:
				idx = N
			remove_ones = ps[-1] - ps[idx]
			remove_ones -= (N - idx) * (small + K)
			answer = min(answer, remove_all + remove_ones)
		return answer


def upper_bound(A, L, R, K):
	pos = R + 1
	while L <= R:
		mid = (L + R) // 2
		if A[mid] > K:
			pos = mid
			R = mid - 1
		else:
			L = mid + 1
	return pos

class Solution:

	def minSteps(self, A, N, K):
		ans = sum(A)
		prefix_sum = [0 for i in range(0, N + 1)]
		A.sort()
		prefix_sum[0] = A[0]
		for i in range(1, N):
			prefix_sum[i] = prefix_sum[i - 1] + A[i]
		last_remove = 0
		for i in range(0, N):
			if i > 0 and A[i] != A[i - 1]:
				last_remove = prefix_sum[i - 1]
			first_reduce = upper_bound(A, i, N - 1, A[i] + K)
			ans = min(ans, last_remove + prefix_sum[N - 1] - prefix_sum[first_reduce - 1] - (N - first_reduce) * (A[i] + K))
		return ans


import bisect

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		prefix_sum = [0] * (N + 1)
		for i in range(1, N + 1):
			prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
		ans = prefix_sum[-1]
		for i in range(N):
			steps = 0
			x = A[i] + K
			s_ind = bisect.bisect_right(A, x, i + 1, N) - 1
			actual_sum = prefix_sum[N] - prefix_sum[s_ind + 1]
			required_sum = (N - 1 - s_ind) * (A[i] + K)
			steps = actual_sum - required_sum + prefix_sum[i]
			ans = min(steps, ans)
		return ans


import bisect

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		p = [0] * N
		p[0] = A[0]
		for i in range(1, N):
			p[i] = p[i - 1] + A[i]
		res = 1000000000
		start = 0
		for i in range(N):
			index = bisect.bisect_right(A, A[i] + K, lo=0, hi=len(A))
			if i > 0 and A[i] != A[i - 1]:
				start = p[i - 1]
			res = min(res, start + p[N - 1] - p[index - 1] - (N - index) * (A[i] + K))
		return res


def upbound(A, L, R, value):
	pos = R + 1
	while L <= R:
		mid = (L + R) // 2
		if A[mid] > value:
			pos = mid
			R = mid - 1
		else:
			L = mid + 1
	return pos

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		prefix = [0] * N
		prefix[0] = A[0]
		for i in range(1, N):
			prefix[i] = prefix[i - 1] + A[i]
		res = (1 << 31) - 1
		upto = 0
		for i in range(N):
			pos = upbound(A, i, N - 1, A[i] + K)
			if i > 0 and A[i] != A[i - 1]:
				upto = prefix[i - 1]
			res = min(res, upto + prefix[N - 1] - prefix[pos - 1] - (N - pos) * (A[i] + K))
		return res


import sys

class Solution:

	def minSteps(self, a, n, k):
		a.sort()
		suma = [0] * n
		suma[0] = a[0]
		ans = sys.maxsize
		for i in range(1, n):
			suma[i] = suma[i - 1] + a[i]
		for i in range(n):
			res = 0
			key = a[i] + k
			num = self.bs(a, key, i + 1, n - 1)
			if num != -1:
				ind = n - 1 - (num - 1)
				res = suma[n - 1] - suma[num - 1]
				res = res - key * ind
			if i > 0:
				res += suma[i - 1]
			ans = min(ans, res)
		return ans

	def bs(self, arr, k, l, h):
		res = -1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] <= k:
				l = mid + 1
			else:
				res = mid
				h = mid - 1
		return res


class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		ps = [0] * N
		res = 1 << 32 - 1
		ps[0] = A[0]
		for i in range(1, N):
			ps[i] = ps[i - 1] + A[i]

		def upperbound(l, con):
			r = N - 1
			pos = N
			while l <= r:
				m = (l + r) // 2
				if A[m] > con:
					pos = m
					r = m - 1
				else:
					l = m + 1
			return pos
		prev = 0
		for i in range(N):
			SUM = 0
			pos = upperbound(i, A[i] + K)
			SUM += ps[N - 1] - ps[pos - 1] - (N - pos) * (A[i] + K)
			if i > 0 and A[i] != A[i - 1]:
				prev = ps[i - 1]
			res = min(res, prev + SUM)
		return res


class Solution:

	def find_coins_to_be_removed(self, start, end, A, K, mini):
		coins = 0
		for i in range(start, end + 1):
			z = A[i] - mini
			if z > K:
				coins += z - K
		return coins

	def minSteps(self, a, n, k):
		import bisect
		import sys
		a.sort()
		prefixsum = [0] * n
		prefixsum[0] = a[0]
		res = sys.maxsize
		for i in range(1, n):
			prefixsum[i] = a[i] + prefixsum[i - 1]
		for i in range(n):
			if i == 0:
				ind = bisect.bisect_right(a, a[i] + k)
				res = min(res, prefixsum[n - 1] - prefixsum[ind - 1] - (n - ind) * (a[i] + k))
			elif i != n - 1:
				ind = bisect.bisect_right(a, a[i] + k)
				res = min(res, prefixsum[i - 1] + (prefixsum[n - 1] - prefixsum[ind - 1] - (n - ind) * (a[i] + k)))
			else:
				res = min(res, prefixsum[i - 1])
		return res


import bisect

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pre = 0
		s = sum(A)
		pre_s = []
		for i in A:
			if len(pre_s) == 0:
				pre_s.append(i)
			else:
				pre_s.append(i + pre_s[-1])
		coins = float('inf')
		for i in range(len(A)):
			if i != 0 and A[i] == A[i - 1]:
				pre += A[i]
				continue
			index = bisect.bisect_right(A, A[i] + K)
			if index > N:
				index = N
			temp = s - pre_s[index - 1]
			temp = temp - (A[i] + K) * (N - index)
			coins = min(coins, pre + temp)
			pre += A[i]
		return coins

	def binarySearch(self, arr, target, low, high):
		res = -1
		while low <= high:
			mid = (low + high) // 2
			if A[mid] > target:
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


import bisect

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		p = [0] * N
		p[0] = A[0]
		for i in range(1, N):
			p[i] = p[i - 1] + A[i]
		ans = float('inf')
		start = 0
		for i in range(N):
			index = bisect.bisect(A, A[i] + K)
			if i > 0 and A[i] != A[i - 1]:
				start = p[i - 1]
			ans = min(ans, start + (p[N - 1] - p[index - 1] - (A[i] + K) * (N - index)))
		return ans


from bisect import bisect_right

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		prefix_sum = [0] * N
		prefix_sum[0] = A[0]
		ans = float('inf')
		for i in range(1, N):
			prefix_sum[i] = A[i] + prefix_sum[i - 1]
		for i in range(N):
			index = bisect_right(A, A[i] + K)
			if index < N:
				f_coins = prefix_sum[N - 1] - prefix_sum[index - 1]
				f_coins = f_coins - (N - index) * (A[i] + K)
			else:
				f_coins = 0
			if i > 0:
				p_coins = prefix_sum[i - 1]
			else:
				p_coins = 0
			ans = min(ans, f_coins + p_coins)
		return ans


class Solution:

	def minSteps(self, a, n, k):
		a = sorted(a)
		p0 = 0
		r0 = 0
		p1 = len(a) - 1
		r1 = 0
		while a[p1] - k - a[p0] > 0:
			r1 += a[p1] - k - a[p0]
			p1 -= 1
		p1 += 1
		memo = [r0 + r1]
		while p0 + 1 < len(a):
			p0 += 1
			r0 += a[p0 - 1]
			ap = a[p1 - 1]
			while p1 < len(a):
				if k + a[p0] - a[p1] > 0:
					r1 -= a[p1] - (k + a[p0 - 1])
					p1 += 1
				else:
					break
			r1 -= (len(a) - p1) * (a[p0] - a[p0 - 1])
			memo.append(r0 + r1)
		return min(memo)


class Solution:

	def binary(self, a, k, x, low, high):
		tar = x + k
		ans = low - 1
		while low <= high:
			mid = (low + high) // 2
			if a[mid] <= tar:
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return ans

	def minSteps(self, a, n, k):
		if n == 1:
			return 0
		a.sort()
		pre = [0] * n
		pre[0] = a[0]
		for i in range(1, n):
			pre[i] = pre[i - 1] + a[i]
		total = pre[-1]
		z = self.binary(a, k, a[0], 1, n - 1)
		ans = min(total, total - pre[z] - (n - z - 1) * (k + a[0]))
		for i in range(1, n):
			z = self.binary(a, k, a[i], i + 1, n - 1)
			ans = min(ans, total - pre[z] + pre[i - 1] - (n - z - 1) * (k + a[i]))
		return ans


import bisect as bt

class Solution:

	def minSteps(self, A, N, K):
		(n, k) = (N, K)
		A.sort()
		pfs = [A[0]]
		for i in A[1:]:
			pfs.append(i + pfs[-1])
		sm = pfs[-1]
		ans = float('inf')
		for i in range(n):
			mn = A[i]
			temp = pfs[i] - A[i]
			ix = bt.bisect_left(A, mn + k + 1, i + 1, n)
			if ix < n:
				temp += sm - pfs[ix] + A[ix] - (n - ix) * (mn + k)
			ans = min(ans, temp)
		return ans


import bisect

class Solution:

	def minSteps(self, l, n, k):
		if n == 1:
			return 0
		l.sort()
		t = [l[i] for i in range(n)]
		for i in range(n - 2, -1, -1):
			t[i] += t[i + 1]
		ans = sum(l) - l[-1]
		c = 0
		for i in range(n - 1):
			j = bisect.bisect_left(l, l[i] + k + 1)
			if j == n:
				ans = min(ans, c)
				break
			ans = min(ans, c + t[j] - (n - j) * (l[i] + k))
			c += l[i]
		return ans


class Solution:

	def _nextGreaterThanX(self, arr, start_idx, x):
		(left, right) = (start_idx + 1, len(arr) - 1)
		ans = len(arr)
		while left <= right:
			mid = left + (right - left) // 2
			if arr[mid] > x:
				ans = min(ans, mid)
				right = mid - 1
			else:
				left = mid + 1
		return ans

	def minSteps(self, A, N, K):
		A.sort()
		prefix_sum = [0] * N
		_sum = 0
		ans = float('inf')
		if N == 1:
			return 0
		if A[-1] - A[0] <= K:
			return 0
		for (idx, val) in enumerate(A):
			_sum += val
			prefix_sum[idx] = _sum
		for (idx, val) in enumerate(A):
			greater_ele_idx = self._nextGreaterThanX(A, idx, val + K)
			remove_coins = None
			if greater_ele_idx == len(A):
				remove_coins = prefix_sum[idx - 1] if idx > 0 else 0
			else:
				a = prefix_sum[len(A) - 1] - prefix_sum[greater_ele_idx - 1]
				b = (len(A) - greater_ele_idx) * (val + K)
				remove_coins = a - b + (prefix_sum[idx - 1] if idx > 0 else 0)
			ans = min(ans, remove_coins)
		return ans


from bisect import bisect_left

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pre = [0]
		for i in A:
			pre.append(pre[-1] + i)
		ans = pre[-1]
		remove = 0
		re = 0
		for up in range(A[-1], 0, -1):
			re += remove
			a = bisect_left(A, up - K)
			ans = min(ans, re + pre[a])
			if a == 0:
				break
			while A[-remove - 1] == up:
				remove += 1
		return ans


from functools import lru_cache

@lru_cache(None)
def count(arr, k, i, j):
	print('i = ', i, 'j = ', j)
	if arr[j] - arr[i] <= k:
		return 0
	m = i + 1
	while m <= j and arr[m] == arr[i]:
		m += 1
	n = j - 1
	while n >= i and arr[n] == arr[j]:
		n -= 1
	return min(m - i + count(arr, k, m, j), j - n + count(arr, k, i, n))

@lru_cache(None)
def remove(arr, k, idx):
	if idx == len(arr) - 1:
		return 0
	r = 0
	for i in range(len(arr) - 1, idx, -1):
		if arr[i] - arr[idx] <= k:
			break
		r += arr[i] - arr[idx] - k
	return min(r, arr[idx] + remove(arr, k, idx + 1))
from itertools import accumulate
from bisect import bisect_left

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		prefix = [0] + list(accumulate(A))
		ans = prefix[-1]
		speed = 0
		remove = 0
		for upper in range(A[-1], 0, -1):
			remove += speed
			i = bisect_left(A, upper - K)
			ans = min(ans, remove + prefix[i])
			if i == 0:
				break
			while A[-speed - 1] == upper:
				speed += 1
		return ans


from bisect import bisect_left

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		prefix_sum = [0]
		for x in A:
			prefix_sum.append(prefix_sum[-1] + x)
		ans = prefix_sum[-1]
		remove_speed = 0
		remove = 0
		for upper in range(A[-1], 0, -1):
			remove += remove_speed
			i = bisect_left(A, upper - K)
			ans = min(ans, remove + prefix_sum[i])
			if i == 0:
				break
			while A[-remove_speed - 1] == upper:
				remove_speed += 1
		return ans


from bisect import bisect_left

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pre = [0]
		for i in A:
			pre.append(pre[-1] + i)
		res = pre[-1]
		speed = 0
		remove = 0
		for upper in range(A[-1], 0, -1):
			remove += speed
			i = bisect_left(A, upper - K)
			res = min(res, remove + pre[i])
			if i == 0:
				break
			while A[-speed - 1] == upper:
				speed += 1
		return res


class Solution:

	def binary(self, A, x, n):
		l = 0
		h = n - 1
		ans = 0
		while l <= h:
			mid = (l + h) // 2
			if A[mid] <= x:
				l = mid + 1
			else:
				h = mid - 1
				ans = mid
		return ans

	def minSteps(self, A, N, K):
		A.sort()
		l = [0]
		l.append(A[0])
		for i in range(1, N):
			l.append(A[i] + l[-1])
		prev = 0
		ans = float('inf')
		for i in range(N):
			if A[i] + K >= A[-1]:
				ans1 = N
			else:
				ans1 = self.binary(A, A[i] + K, N)
			if i > 0 and A[i] != A[i - 1]:
				prev = l[i]
			ans = min(ans, prev + l[N] - l[ans1] - (N - ans1) * (A[i] + K))
		return ans


from bisect import bisect_right

class Solution:

	def minSteps(self, A, N, k):
		A.sort()
		prevsum = [0] * (N + 1)
		ans = 99999999
		for i in range(1, N + 1):
			prevsum[i] = prevsum[i - 1] + A[i - 1]
		for i in range(0, N):
			index = bisect_right(A, A[i] + k)
			psum = prevsum[N] - prevsum[index]
			rsum = (N - index) * (A[i] + k)
			count = psum - rsum
			count += prevsum[i]
			ans = min(count, ans)
		return ans


from bisect import bisect_left

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pr = [0]
		for x in A:
			pr.append(pr[-1] + x)
		ans = pr[-1]
		rs = 0
		r = 0
		for u in range(A[-1], 0, -1):
			r += rs
			i = bisect_left(A, u - K)
			ans = min(ans, r + pr[i])
			if i == 0:
				break
			while A[-rs - 1] == u:
				rs += 1
		return ans


import heapq
import bisect

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		pre = [0]
		for i in A:
			pre.append(pre[-1] + i)
		ans = pre[-1]
		sp = 0
		remove = 0
		for i in range(A[-1], 0, -1):
			remove += sp
			x = bisect.bisect_left(A, i - K)
			ans = min(ans, remove + pre[x])
			if x == 0:
				break
			while A[-sp - 1] == i:
				sp += 1
		return ans


from itertools import *
import bisect

class Solution:

	def minSteps(self, arr, n, k):
		ans = float('inf')
		arr.sort()
		pref = list(accumulate(arr))
		for i in range(n):
			p = bisect.bisect_right(arr, arr[i] + k)
			if i == 0 and p == n:
				return 0
			if p == n:
				ans = min(ans, pref[i - 1])
			elif i == 0:
				ans = min(ans, pref[-1] - pref[p - 1] - (arr[i] + k) * (n - p))
			else:
				ans = min(ans, pref[i - 1] + pref[-1] - pref[p - 1] - (arr[i] + k) * (n - p))
		return ans


from bisect import bisect_left

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		presum = [0]
		for i in A:
			presum.append(presum[-1] + i)
		res = presum[-1]
		remspeed = 0
		rem = 0
		for i in range(A[-1], 0, -1):
			rem += remspeed
			j = bisect_left(A, i - K)
			res = min(res, rem + presum[j])
			if j == 0:
				break
			while A[-remspeed - 1] == i:
				remspeed += 1
		return res


import bisect

class Solution:

	def minSteps(self, arr, n, k):
		arr.sort()
		prefix = [0]
		for i in range(0, n):
			prefix.append(prefix[-1] + arr[i])
		ans = prefix[-1]
		remove = 0
		speed = 0
		for upper in range(arr[-1], 0, -1):
			remove += speed
			ind = bisect.bisect_left(arr, upper - k)
			ans = min(ans, remove + prefix[ind])
			if ind == 0:
				break
			while arr[-speed - 1] == upper:
				speed += 1
		return ans


from bisect import bisect_left, bisect_right
from math import inf

class Solution:

	def minSteps(self, A, N, K):
		A.sort()
		cache = [0] * len(A)
		for i in range(len(A) - 1, -1, -1):
			cache[i] += A[i] + cache[i + 1] if i + 1 < len(A) else A[i]
		prev_sum = 0
		ans = inf
		for x in A:
			index = bisect_right(A, x + K)
			cand = 0
			if index < len(A):
				cand = cache[index] - (len(A) - index) * (x + K)
			ans = min(ans, cand + prev_sum)
			prev_sum += x
		return ans


class Solution:

	def minSteps(self, arr, n, k):
		f = [[0, 0, 0]]
		arr = arr[:n]
		arr.sort()
		i = 0
		while i < n:
			f.append([arr[i], 1, f[-1][2] + arr[i]])
			i += 1
			while i < n and arr[i] == arr[i - 1]:
				f[-1][1] += 1
				f[-1][2] += arr[i]
				i += 1
		ans = f[-1][2]
		for i in range(1, len(f)):
			l = f[i][0]
			r = min(f[-1][0], l + k)
			s = f[i - 1][2]
			j = len(f) - 1
			while j > i and f[j][0] > r:
				s += (f[j][0] - r) * f[j][1]
				j -= 1
			ans = min(ans, s)
		return ans


import math
from collections import Counter
import bisect

class Solution:

	def minSteps(self, a, n, k):
		mp = Counter(a)
		(a, n) = (sorted(mp.keys()), len(mp))
		if n == 1:
			return 0
		ps = [a[0] * mp[a[0]]] + [0] * (n - 1)
		pcnt = [mp[a[0]]] + [0] * (n - 1)
		for i in range(1, n):
			ps[i] = ps[i - 1] + a[i] * mp[a[i]]
			pcnt[i] = pcnt[i - 1] + mp[a[i]]
		ans = math.inf
		for i in range(n):
			j = bisect.bisect_right(a, a[i] + k)
			cnt = pcnt[n - 1] - pcnt[j - 1]
			sm = ps[n - 1] - ps[j - 1] - cnt * (a[i] + k)
			if i > 0:
				sm += ps[i - 1]
			ans = min(ans, sm)
		return ans


class Solution:

	def findIndex(self, A, i, N, p):
		l = i + 1
		h = N - 1
		while l <= h:
			m = (l + h) // 2
			if A[m] <= p:
				l = m + 1
			else:
				h = m - 1
		return l
		return N

	def minSteps(self, A, N, K):
		d = [0] * N
		A.sort()
		d[0] += A[0]
		for i in range(1, N):
			d[i] += d[i - 1] + A[i]
		ans = 9999999999999999
		prev = 0
		c = 1
		for i in range(N):
			if i + 1 < N and A[i] == A[i + 1]:
				c += 1
				i += 1
				continue
			p = A[i] + K
			idx = self.findIndex(A, i, N, p)
			actualSum = d[N - 1] - d[idx - 1]
			reduc = (N - idx) * p
			actualSum -= reduc
			ans = min(ans, actualSum + prev)
			prev += A[i] * c
			c = 1
		return ans