C. 3-н бааз станц

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Шинэ Васжуки тосгон нь авто тээврийн зам хүртэл тэлсэн бөгөөд иймээс уг тосгоны байшин бүрийг $x_{i}$ координат бүхий цэгээр дүрсэлж болох юм. Уг тосгон нь $n$ ширхэг байшингаас тогтох бөгөөд $i$-дахь байшин нь $x_{i}$ гэсэн координаттай цэг дээр байрласан байна.

Үүрэн харилцаа холбооны сүлжээ нэвтрүүлэгч TELE3 төхөөрөмжийг 3-н бааз станцад байрлуулахаар төлөвлөсөн бөгөөд ингэснээр уг тосгон доторх байшин бүр нь үүрэн харилцаа холбооны сүлжээгээр хангагдах юм. $t$ цэг дээр байрлалтай $d$ хүчин чадалтай бааз станц нь $[t - d, t + d]$ хэрчим дээр орших (захын цэгүүд нь мөн багтана) бүх байшингуудыг сүлжээгээр хангах юм.

Уг бодлогыг хялбар болгох үүднээс бүх 3-н бааз станцуудыг ижилхэн $d$ хүчин чадалтай гэж үзнэ үү. Тэгвэл тосгоны бүх байшинг сүлжээгээр хангахын тулд шаардагдах хамгийн бага $d$-ын утгыг олно уу.

Оролт

Эхний мөрөнд тосгоны байшингуудын тоог илэрхийлэх бүхэл тоо $n$ ($1 ≤ n ≤ 2*10^{5}$) өгөгдөнө. 2-дахь мөрөнд байшингуудын координатууд болох бүхэл тоонуудын $x_{1}, x_{2}, ..., x_{n}$ ($1 ≤ x_{i} ≤ 10^{9}$) дараалал өгөгдөнө. 2 болон түүнээс дээш тооны байшингууд нэг цэг дээр байрласан байх боломжтой. Түүнчлэн байшингуудын координатууд нь дурын дарааллаар өгөгдөнө.

Гаралт

Хамгийн бага шаардлагатай хүчин чадал $d$-ын утгыг хэвлэнэ үү. 2-дахь мөрөнд бааз станцуудын боломжит байрлалууд буюу координатуудыг илэрхийлэх 3 тоог хэвлэнэ үү. Координатуудыг хэвлэхдээ таслалаас хойш 6-н орны нарийвчлалтай хэвлэнэ. Станцуудын байрлалууд нь $0$-ээс $2*10^{9}$-ын хооронд болон эдгээр 2 цэг дээр байж болно. Түүнчлэн бааз станцууд нь ижил координат бүхий цэгүүд дээр байрлаж болох бөгөөд уг бодлогыг бодох олон шийдэл байвал та тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4
1 2 3 4
Гаралт
0.500000
1.500000 2.500000 3.500000
Оролт
3
10 20 30
Гаралт
0
10.000000 20.000000 30.000000
Оролт
5
10003 10004 10001 10002 1
Гаралт
0.500000
1.000000 10001.500000 10003.500000
Сэтгэгдлүүдийг ачааллаж байна...