Chuồng bò của bác John có một mặt là hàng rào và những con bò của bác John thường xuyên chui qua hàng rào để đi chơi. Hàng rào của bác John có thể coi là một đường thẳng trên đó trồng \(N\) cọc gỗ đánh số từ \(1\) tới \(N\), cọc gỗ thứ \(i\) ở vị trí số nguyên \(x_i\). Một con bò có thể chui qua hàng rào ở vị trí giữa hai cọc gỗ nếu chiều ngang của nó nhỏ hơn hoặc bằng khoảng cách giữa hai cọc.

Để ngăn các con bò trốn chuồng đi chơi, bác John quyết định mua thêm các cọc gỗ để trồng vào giữa hàng rào đang có, vị trí trồng cọc mới phải là số nguyên. Do ngân sách hạn hẹp, bác John chỉ có thể mua thêm tối đa \(K\) cọc gỗ mà thôi. Tuy vậy có thể có những con bò đủ nhỏ để chui qua hàng rào dù cho bác John có trồng thêm các cọc gỗ vào vị trí nào đi nữa.

Yêu cầu: Tìm số nguyên \(w\) thỏa mãn: Một con bò có chiều ngang \( ≤ w\) có thể chui qua rào dù cho bác John có trồng thêm các cọc gỗ ở trị trí nào đi nữa.

Input

• Dòng 1 chứa hai số nguyên \(N, K (2 ≤ N ≤ 10^5; 0 ≤ K ≤ 10^9\)).

• Dòng 2 chứa \(N\) số nguyên phân biệt \(x_1, x_2, ..., x_N (|x_i| ≤ 10^9)\).

Output

Ghi một số nguyên duy nhất là giá trị \(w\) tìm được.

Sample INput

3 3
1 8 19

Sample Output

4

Sample INput

1 10
1 2 3

Sample Output

1