我们都知道罗宾汉令人印象深刻的故事。罗宾汉利用他的射箭技巧和智慧从富人那里偷走钱财,然后返还给穷人。
Kekoland有n位公民,每人有ci币。罗宾汉每天都会从城里最富有的人那里拿走 1 个硬币,然后把它送给最穷的人(在拿走最富有的人的 1 个硬币后立即变成最穷的人)。如果选择不唯一,他会随机选择其中之一。遗憾的是,罗宾汉年纪大了,想在k天后退休。他决定用这最后的日子来帮助穷人。
在他的钱被罗宾汉拿走之后,最富有的人也可能成为最穷的人,甚至可能发生罗宾汉将他的钱还回来的情况。例如,如果所有人都有相同数量的硬币,那么第二天他们也会拥有相同数量的硬币。
你的任务是找出 k 天后最富有的人和最贫穷的人的财富之间的差异。请注意,在最富有和最贫穷的人中随机选择不会影响答案。
输入
输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 500 000, 0 ≤ k ≤ 109) - Kekoland 的公民数量以及罗宾汉退休前的剩余天数。
第二行包含n个整数,其中第i个是ci (1 ≤ ci ≤ 109)——第i个人的初始财富。
输出
打印一行,其中包含最富有和最贫穷人口之间的财富差异。
示例
输入 #1
4 1 1 1 4 2
输出 #1
2
输入 #2
3 1 2 2 2
输出 #2
0
注意
让我们看看第一个样本中财富每天如何变化。
1. [1, 1, 4, 2]
2. [2, 1, 3, 2] 或 [1, 2, 3, 2]
所以答案是 3 - 1 = 2
在第二个样本中,每个人的财富将保持不变。