← 返回题目列表

Codeforces · 671/B

B. 罗宾汉

中文机器翻译题面 查看原题

我们都知道罗宾汉令人印象深刻的故事。罗宾汉利用他的射箭技巧和智慧从富人那里偷走钱财,然后返还给穷人。

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

在第二个样本中,每个人的财富将保持不变。