Công ty điện lực cần lắp đặt đúng \(K\) cột đèn đường trên con đường dài \(L\) km (từ vị trí \(0\) đến \(L\)). Có \(N\) ngôi làng cần được chiếu sáng ở các vị trí nguyên \(p_1, p_2, \ldots, p_N\) (\(1 \le p_i < L\), các vị trí khác nhau) nằm trong khoảng \([1, L-1]\). Mỗi cột đèn đặt tại vị trí \(x\) (nguyên) phủ sáng mọi vị trí trong đoạn \([x - R, x + R]\). Công ty sẽ đặt đúng \(K\) cột ở các vị trí khác nhau. Hãy tìm bán kính \(R\) nhỏ nhất để mọi ngôi làng đều được chiếu sáng.

Định dạng đầu vào

• Dòng đầu chứa \(N\), \(K\) và \(L\) (\(1 \le N \le 10^5\), \(1 \le K \le 10^5\), \(K \le N\), \(N + 2 \le L \le 10^{18}\)).
• Dòng thứ hai chứa \(N\) số nguyên \(p_1, p_2, \ldots, p_N\) (\(1 \le p_i < L\), phân biệt).

Định dạng đầu ra

• In ra một số nguyên là bán kính phủ \(R\) tối thiểu.

Ví dụ

Input:

3 2 100
10 30 70

Output:

30

Giải thích: Với \(R = 30\):

• Đặt cột tại \(40\): phủ \([10, 70]\) chứa \(10, 30, 70\).
• Đặt cột tại vị trí bất kỳ khác \(40\).

Với \(R < 30\) thì \(K = 2\) không đủ.

Ràng buộc

• \(1 \le N \le 10^5\), \(1 \le K \le N\).
• \(N + 2 \le L \le 10^{18}\).
• \(1 \le p_i < L\).