Robin Hood

题面翻译

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

在Kekoland有n个公民，每个人都有ci 的钱币。每天，罗宾汉将从城里最富有的人身上拿出1 枚硬币，他会把它交给最贫穷的人。如果选择不是唯一的，他将随机选择其中一个。可悲的是，罗宾汉已经老了，想要在第k 天退休。他决定在最后几天帮助穷人。

罗宾汉拿走他的钱后，最富有的人也可能成为最穷的人，甚至可能会发生罗宾汉将他的钱还给他的钱。例如，如果所有人拥有相同数量的硬币，那么第二天他们也将拥有相同数量的硬币。

输出第k 天最富有的人和最穷的人硬币数量之间的差值。 （第k天罗宾汉也交换了钱）

题目描述

We all know the impressive story of Robin Hood. Robin Hood uses his archery skills and his wits to steal the money from rich, and return it to the poor.

There are $n$ citizens in Kekoland, each person has $c_{i}$ coins. Each day, Robin Hood will take exactly $1$ coin from the richest person in the city and he will give it to the poorest person (poorest person right after taking richest's $1$ coin). In case the choice is not unique, he will select one among them at random. Sadly, Robin Hood is old and want to retire in $k$ days. He decided to spend these last days with helping poor people.

After taking his money are taken by Robin Hood richest person may become poorest person as well, and it might even happen that Robin Hood will give his money back. For example if all people have same number of coins, then next day they will have same number of coins too.

Your task is to find the difference between richest and poorest persons wealth after $k$ days. Note that the choosing at random among richest and poorest doesn't affect the answer.

输入格式

The first line of the input contains two integers $n$ and $k$ ( $1<=n<=500000,0<=k<=10^{9}$ ) — the number of citizens in Kekoland and the number of days left till Robin Hood's retirement.

The second line contains $n$ integers, the $i$ -th of them is $c_{i}$ ( $1<=c_{i}<=10^{9}$ ) — initial wealth of the $i$ -th person.

输出格式

Print a single line containing the difference between richest and poorest peoples wealth.

样例 #1

样例输入 #1

4 1
1 1 4 2

样例输出 #1

2

样例 #2

样例输入 #2

3 1
2 2 2

样例输出 #2

0

提示

Lets look at how wealth changes through day in the first sample.

1. $[1,1,4,2]$
2. $[2,1,3,2]$ or $[1,2,3,2]$

So the answer is $3-1=2$

In second sample wealth will remain the same for each person.