D. Robin Hood

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 ci 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.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 500 000, 0 ≤ k ≤ 109) — 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 ci (1 ≤ ci ≤ 109) — initial wealth of the i-th person.

Output

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

INPUT

4 1 

1 1 4 2

OUTPUT

2

 **************************** explanation****************

For k<=100000 we could have implemented the simulation using set or other data strucutres. But since a linear time algorithm is not possible it hints us towards binary search.
What do we do?

(1) This is a greedy logic by which we try to decreas the maximum as much as possible and increase the minimum . Due to convex nature of the function we can easily use binary search. Now we need to fix maximum and minimum . let that be mid now all values less greater than mid should strictly loose the necessary coins and that less than mid may or may not gain those coins. Hence if give is summation of all values by the amount of which it is greater than mid then give must be <=k and it must be >=take.

similalry we can do this for maximising the minima..

FOLLOW THE CODE

       *******************BELOW IS THE CODE ***********************************************

#include<bits/stdc++.h>

using namespace std;

/*      my general mistakes that costed me a lot

          * check for overflows

          * check and mod and use int type variables where possible to avoid tles

          * while multiplying two variables whose value can exceed integer 

          limt make sure to typecase them

          * use scanf when you are not working with the best possible optimisation

          * return a value from a function that has a return type sometimes the 

          compiler may give the correct answer but there will be problem in the judge

          * be very cautious about uninitiaalised variables , infact never keep them

          or handle them properly*/

#define ff first

#define ss second

#define mp make_pair

#define pb push_back

#define ll long long int

#define pp pair<int,int> 

#define ve vector

#define mod 1000000007

/************************************CODE BEGINS HERE************************/

int a[1000010];

int main()

{

         int n;

         cin>>n;

         int k;

         cin>>k;

         int mx=0;

         int mi=2000000000;

         for(int i=0;i<n;i++)

         {

            scanf("%d",&a[i]);

            mx=max(a[i],mx);

            mi=min(a[i],mi);

 }

 ll low=0;

 ll high=mx+2;

 ll ans=mx;

 

 while(low<high)

 {

       ll can=0;

       ll mid=(low+high)/2;

       //cout<<"mid "<<mid<<endl;

       ll give=0;

       ll take=0;

       for(int i=0;i<n;i++)

       {

             if(a[i]>mid)

 {

  give+=a[i]-mid;

 }

 else take+=mid-a[i];

 }

 if(give<=k && take>=give)

 {

    high=mid;

    ans=mid;

 }

 else low=mid+1;

 }

//  cout<<"ans "<<ans<<endl;

 low=0;

 high=2000000000;

 ll ans2=mi;

 while(low<high)

 {

    ll give=0;

    ll take=0;

    ll mid=(low+high)/2;

for(int i=0;i<n;i++)

    {

    

    // cout<<"mid "<<mid<<endl;

          if(a[i]>mid)

  {

      give+=a[i]-mid;

  } 

  else take+=mid-a[i];

}

  if(take<=k && give>=take )

  {

//   cout<<"can "<<endl;

       ans2=mid;

low=mid+1;

  }

  else high=mid;

 }

//  cout<<"ans2 "<<ans2<<endl;

 cout<<ans-ans2<<endl;

 return 0;

}