ami không làm gì mà vẫn có rất nhiều tiền. ami để tiền của mình trong \(n\) cái lọ, lọ \(i\) có \(a_i\) triệu USD. Quá rảnh rỗi, mỗi ngày ami sẽ làm đúng 1 lần thao tác sau:

1. Chọn một lọ \(i\) mà \(a_i\) là lớn nhất và rút ra một triệu USD (\(a_i = a_i - 1\)).
2. ami sẽ cầm 1 triệu USD đó bỏ vào lọ \(i\) có ít tiền nhất.

Ví dụ, với |2 2 2|, ami có thể chọn lọ 1, số tiền lúc này còn lại là |1 2 2|. Lọ có ít tiền nhất là lọ 1. ami sẽ bỏ lại 1 triệu USD này vào lại lọ 1 và nhận được |2 2 2|.

Với |3 1 3|, ami có thể chọn lọ 3, số tiền lúc này còn lại là |3 1 2|. Lọ có ít tiền nhất là lọ 2. ami sẽ bỏ 1 triệu USD này vào lọ 2 và nhận được |3 2 2|.

Sau khi làm việc này trong \(k\) ngày, ami muốn các bạn tính giá trị \(max - min\). Với \(max\) là số tiền nhiều nhất trong 1 lọ (\(a_i\) lớn nhất) và \(min\) là số tiền ít nhất trong 1 lọ (\(a_i\) ít nhất). Dễ dàng nhận thấy với một dãy \(A\) bất kì và số \(k\) cố định, giá trị \(max - min\) luôn chỉ có 1.

Input

• Dòng đầu chứa 2 số nguyên dương \(n\) và \(k\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) là số tiền trong lọ \(i\).

Output

• Một số nguyên là \(max - min\).

Example

3 1
18 18 18

0

3 3
15 16 20

0

Giới hạn

• Trong tất cả các test, \(k \leq 10^9\).
• \(33\%\) test có \(1 \leq n, a_i \leq 100\).
• \(33\%\) test có \(1 \leq n, a_i \leq 1000\).
• \(34\%\) test có \(1 \leq n \leq 300000\), \(a_i \leq 10^9\).