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 thực trên đó trồng \(n\) cọc gỗ đánh số từ \(1\) tới \(n\), cọc gỗ thứ \(i\) ở vị trí là số nguyên \(x_i\). Một con bò chỉ có thể chui qua 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. (Con bò không thể đi vòng qua rào, bởi vì cọc gỗ có vị trí nhỏ nhất và cọc gỗ có vị trí lớn nhất được trồng sát tường của chuồng).

Để 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 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ọi con bò có chiều ngang \(\leq w\) có thể chui qua rào cho dù bác John có trồng thêm các cọc ở vị trí nào đi nữa.

Input

Vào từ file văn bản FENCE.INP

• Dòng 1 chứa hai số nguyên \(n, k (2 \leq n \leq 10^5; 0 \leq 𝑘 \leq 10^9)\).
• Dòng 2 chứa \(n\) số nguyên phân biệt \(x_1, x_2,\ldots , x_n (\forall i: |x_i| \leq 10^9)\).

Output

• Ghi ra file văn bản FENCE.OUT một số nguyên duy nhất là giá trị \(w\) tìm được.

Example

3 3
1 8 19

4

3 10
1 2 3

1