Quang đang dự định mua một ngôi nhà mới tại Linecity. Thành phố Linecity nằm trên hệ trục tọa độ ~Ox~. Có tổng cộng ~L+1~ ngôi nhà trong thành phố được đánh số từ ~0~ đến ~L~, ngôi nhà thứ ~i~ có tọa độ ~i~. Trong đó, có ~N~ ngôi nhà đã được mua.

Do là một người trầm tính và yêu thích không gian yên tĩnh, Quang đánh giá rằng độ yên tĩnh của ngôi nhà thứ ~i~ là khoảng cách nhỏ nhất từ nó đến một ngôi nhà bất kì khác mà đã được mua. Nói cách khác, độ yên tĩnh của ngôi nhà thứ ~i~ là ~min(|i − j|)~ với mọi ~j~ sao cho ~0 ≤ j ≤ L~ và ngôi nhà ~j~ đã được mua. Hãy giúp Quang tìm mua nhà sao cho độ yên tĩnh của ngôi nhà được mua là lớn nhất có thể.

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên ~L~ và ~N~ ~(1≤L≤10^9,1≤N ≤min(L,10^5))~ - số ngôi nhà và số ngôi nhà đã được mua.
• Dòng thứ hai gồm một dãy ~N~ số nguyên ~A_1,A_2,...,A_N (0 ≤ A_i ≤ L)~ - cho biết tọa độ của các ngôi nhà đã được mua. Dữ liệu vào đảm bảo Không có hai số nào trong dãy trùng nhau.

Kết quả

• In ra độ yên tĩnh lớn nhất của ngôi nhà mua được.

Chấm điểm

• Subtask 1 (50% số điểm): ~L ≤ 10^5,N ≤ 100~
• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm

Ví dụ

Sample Input 1

12 4
2 5 6 12

Sample Output 1

3

Sample Input 2

10 4 
0 2 3 4

Sample Output 2

6

Giải thích

• Trong ví dụ thứ nhất, ta chọn mua ngôi nhà thứ ~9~ với độ yên tĩnh là ~3~.
• Trong ví dụ thứ hai, ta chọn mua ngôi nhà thứ ~10~ với độ yên tĩnh là ~6~.

Nguồn: Free Contest