1116 : รถโรงเรียน (schoolbus)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 32 megabyte(s)

หลังโรงเรียนเลิก นักเรียนได้ขึ้นรถโรงเรียนเพื่อที่จะเดินทางกลับบ้าน บ้านของนักเรียนทุกคนจะตั้งอยู่บนถนนสายเดียวกันหมด โดยมีโรงเรียนตั้งอยู่ที่หัวถนนซึ่งแทนด้วยพิกัด 0 และบ้านของนักเรียนแต่ละคนจะตั้งอยู่ที่พิกัดซึ่งเป็นจำนวนเต็มบวก โดยพิกัดดังกล่าวแทนระยะห่างจากโรงเรียน

โรงเรียนนี้เป็นโรงเรียนที่มีกฎระเบียบเข้มงวดมาก นักเรียนแต่ละคนจะมีหมายเลขประจำตัวตั้งแต่ 
1, 2, 3 เรียงไปเรื่อยๆ และลำดับการลงจากรถของนักเรียนจะต้องเรียงไปตามหมายเลขจากน้อยไปหามาก กล่าวคือ นักเรียนหมายเลข i จะต้องลงจากรถก่อนนักเรียนหมายเลข i+1 เสมอ

รถโรงเรียนจะวิ่งออกจากโรงเรียนไปตามถนนไปเรื่อยๆ และจะจอดเพื่อส่งนักเรียนในบางจุด ซึ่งจุดเหล่านั้นไม่จำเป็นต้องมีพิกัดเป็นจำนวนเต็ม แต่รถจะวิ่งไปในทิศทางเดียว ไม่มีการวิ่งย้อนกลับเด็ดขาด เนื่องจากกฎระเบียบอันเข้มงวดของโรงเรียนทำให้คุณครูไม่สามารถส่งนักเรียนบางคนลงที่บ้านพอดีได้ อย่างไรก็ตาม คุณครูได้พยายามส่งนักเรียนแต่ละคนให้ดีที่สุด โดยคุณครูมีหลักการว่า ให้พิจารณานักเรียนที่จุดลงจากรถอยู่ห่างจากบ้านของตนมากที่สุด คุณครูต้องการให้ระยะห่างนั้นมีค่าน้อยที่สุดเท่าที่จะทำได้

งานของคุณ
จงเขียนโปรแกรมเพื่อรับจำนวนนักเรียน และพิกัดของบ้านของนักเรียนแต่ละคน แล้วคำนวณหาระยะห่างที่น้อยที่สุดที่เป็นไปได้สำหรับนักเรียนที่จุดลงจากรถอยู่ห่างจากบ้านของตนมากที่สุด

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N (≤ N ≤ 1,000,000) แทนจำนวนนักเรียนทั้งหมด

อีก
N บรรทัดต่อมา ในบรรทัดที่ i+1 ระบุจำนวนเต็ม Di (1 ≤ Di ≤ 1,000,000,000) แทนพิกัดของบ้านของนักเรียนหมายเลข i

ข้อมูลส่งออก
มีบรรทัดเดียว ระบุระยะห่างที่น้อยที่สุดที่เป็นไปได้สำหรับนักเรียนที่จุดลงจากรถอยู่ห่างจากบ้านของตนมากที่สุด โดยตอบเป็นทศนิยม 6 ตำแหน่ง

การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 1,000
50% ของข้อมูลทดสอบ จะมี N ≤ 100,000

ที่มา
ค่ายอบรมเตรียมความพร้อมผู้แทนประเทศไทย สำหรับการแข่งขันคอมพิวเตอร์โอลิมปิก พ.ศ. 2554
โจทย์โดย: สุธี เรืองวิเศษ


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3
3
2
1
1.000000
5
5
2
7
8
3
2.500000

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 15 ผู้เยี่ยมชมและ 4 สมาชิก (2 บอท)