คุณกำลังต่อหอคอยจากบล็อกของเล่นร่วมกับหนูน้อย Kostek พวกคุณได้สร้างหอคอยเรียงกันเป็นแถวแล้ว $n$ หอ โดยหอคอยที่ $i$ มีความสูง $h_i$ ตอนนี้ Kostek ต้องการกำหนดเส้นแบ่งเขตระหว่างหอคอยของเขากับหอคอยของคุณ หอคอยที่อยู่ทางซ้ายของเส้นแบ่งเขตจะเป็นของ Kostek และหอคอยที่เหลือทางขวาจะเป็นของคุณ พวกคุณแต่ละคนต้องมีหอคอยอย่างน้อยหนึ่งหอ
พวกคุณกำลังจะเริ่มเล่นเกมถัดไป ซึ่งเริ่มต้นด้วยการที่แต่ละคนวางทหารลาดตระเวนไว้บนหอคอยที่สูงที่สุดของตน เกมจะไม่สนุกเลยหากทหารลาดตระเวนยืนอยู่ในระดับความสูงที่ต่างกันมาก ดังนั้นคุณจึงควรเสนอการแบ่งที่ยุติธรรมที่สุดเท่าที่จะเป็นไปได้ — เลือกเส้นแบ่งเขตเพื่อทำให้ค่าสัมบูรณ์ของผลต่างระหว่างความสูงของหอคอยที่สูงที่สุดของ Kostek กับของคุณมีค่าน้อยที่สุด จงพิมพ์ผลต่างที่น้อยที่สุดนี้
ข้อมูลนำเข้า
บรรทัดแรกมีจำนวนเต็ม $n$ ($2 \le n \le 300\,000$) แทนจำนวนหอคอย
บรรทัดที่สองมีจำนวนเต็ม $n$ ตัวคือ $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$) แทนความสูงของหอคอยที่เรียงติดกันจากซ้ายไปขวา
ข้อมูลส่งออก
พิมพ์จำนวนเต็มหนึ่งตัว — ผลต่างความสูงที่น้อยที่สุดที่เป็นไปได้ระหว่างหอคอยที่สูงที่สุดของคุณกับหอคอยที่สูงที่สุดของ Kostek
ตัวอย่าง
ข้อมูลนำเข้า 1
3 200 333 100
ข้อมูลส่งออก 1
133
ข้อมูลนำเข้า 2
5 5 2 4 1 5
ข้อมูลส่งออก 2
0
ข้อมูลนำเข้า 3
6 5 1 4 4 2 3
ข้อมูลส่งออก 3
1
หมายเหตุ
ในการทดสอบแรก Kostek ควรตั้งเส้นแบ่งเขตระหว่างหอคอยสองหอแรก เขาจะมีหอคอยความสูง $200$ ในขณะที่คุณมีหอคอยความสูง $333$ และ $100$ หอคอยที่สูงที่สุดของแต่ละคนคือ $200$ และ $333$ ดังนั้นผลลัพธ์คือ $133$ ไม่สามารถทำให้ได้ผลต่างที่น้อยกว่านี้ได้
ในการทดสอบที่สอง ไม่ว่าจะแบ่งอย่างไรก็จะได้ผลต่างเป็น $0$
ในการทดสอบที่สาม Kostek ควรตั้งเส้นแบ่งเขตหลังหอคอยที่หนึ่ง ที่สอง หรือที่สาม ผลต่างที่ต้องการคือ $|5 - 4| = 1$ แผนภาพด้านล่างแสดงหนึ่งในความเป็นไปได้ที่เหมาะสมที่สุดเหล่านี้:
