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

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

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

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

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

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

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

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

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