WiFi

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $m$ ngôi nhà trên một con đường thẳng. Nhà có địa chỉ $x$ nằm cách đầu đường đúng $x$ mét. Có thể mua tối đa $k$ điểm truy cập WiFi và đặt chúng tại bất kỳ vị trí thực nào trên đường.

Khoảng cách của một nhà tới mạng là khoảng cách tới điểm truy cập gần nhất. Hãy đặt tối đa $k$ điểm truy cập sao cho khoảng cách lớn nhất của mọi nhà tới điểm truy cập gần nhất là nhỏ nhất.

In bán kính tối ưu với đúng một chữ số sau dấu thập phân.

Input

• Dòng đầu chứa $k,m$.
• $m$ dòng tiếp theo, mỗi dòng chứa địa chỉ một nhà.

Output

In khoảng cách lớn nhất nhỏ nhất có thể, với một chữ số sau dấu thập phân.

Subtask

• Subtask 1 — 20%: $m\le100$.
• Subtask 2 — 30%: $m\le5000$.
• Subtask 3 — 50%: $1\le k$, $1\le m\le10^5$, địa chỉ trong $[0,10^6]$.

Ví dụ

Input

2 3
1
3
10

Output

1.0

Giải thích

Đặt một điểm truy cập ở vị trí $2$ để phủ các nhà $1$ và $3$, và một điểm ở $10$. Khoảng cách lớn nhất là $1.0$ mét.