Equality

4.3

3 votes
Easy
Problem

You are a wizard who is fighting for equality in a magical kingdom. Each person in the kingdom is assigned a number which denotes the amount of magical power he/she possesses. Greater number implies more power and vice-versa. Due to some limitations, you can't randomly change the number assigned to a person. However, You can either add or subtract k from it. The only condition is that you have to execute this spell on each person, should you choose to use it. Your task is to minimize the maximum difference between the numbers assigned to the people and output it.

Input

The first line contains the number of people N and the number K by which you can increase or decrease the number assigned to a person.

The second line contains N space separated integers ai (where 1<=i<=N) denoting the number assigned to the people.

Output

Output the minimum maximum difference possible between the numbers assigned to the people.

Constraints

1 <= N <= 1000000

1 <= <=

1 <= K <= N

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Total no of people in the kingdom = 4.

The original assigned numbers => [1, 10, 5, 15]

Without the spell:

Maximum difference = 15 - 1 = 14

After the Spell:

[1+5, 10-5, 5+5, 15-5] => [6, 5, 10, 10]

Maximum difference = 10 - 5 = 5

Editor Image

?