โจทย์ปัญหา

นักเรียนชั้นปีที่ $1$ ของโรงเรียนมัธยมปลาย JOI มีทั้งหมด $N$ คน โดยมีหมายเลขประจำตัวตั้งแต่ $1$ ถึง $N$

วันหนึ่ง นักเรียนชั้นปีที่ $1$ ทั้ง $N$ คนได้เข้าสอบ คะแนนของนักเรียนคนที่ $i$ ($1 \le i \le N$) คือ $A_i$ คะแนน ทั้งนี้ นักเรียนทั้ง $N$ คนไม่ได้ได้คะแนนเท่ากันทั้งหมด

การแบ่งห้องเรียนในปีการศึกษาหน้าจะถูกกำหนดโดยผลการสอบครั้งนี้ กล่าวคือ จะเลือกจำนวนเต็ม $x$ ขึ้นมาค่าหนึ่ง แล้วแบ่งนักเรียน $N$ คนออกเป็น $2$ ห้องเรียน โดยให้นักเรียนที่ได้คะแนนตั้งแต่ $x$ คะแนนขึ้นไปอยู่ ห้องเรียนพิเศษ และนักเรียนที่ได้คะแนนน้อยกว่า $x$ คะแนนอยู่ ห้องเรียนปกติ

ในการแบ่งนี้ แต่ละห้องเรียนจะต้องมีนักเรียนอย่างน้อย $1$ คน และจะเลือกวิธีการแบ่งที่ทำให้ผลต่างระหว่างจำนวนนักเรียนในห้องเรียนพิเศษกับจำนวนนักเรียนในห้องเรียนปกติมีค่าน้อยที่สุด นอกจากนี้ หากมีวิธีการแบ่งดังกล่าวได้หลายแบบ จะเลือกแบบที่ทำให้จำนวนนักเรียนในห้องเรียนพิเศษมีค่าน้อยที่สุด

เมื่อกำหนดจำนวนนักเรียนและคะแนนของนักเรียนแต่ละคน จงเขียนโปรแกรมเพื่อหาคะแนนต่ำสุดของนักเรียนในห้องเรียนพิเศษ

ข้อจำกัด

• $2 \le N \le 500000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• มี $i, j$ ($1 \le i < j \le N$) ที่ทำให้ $A_i \ne A_j$
• ค่าที่รับเข้ามาทั้งหมดเป็นจำนวนเต็ม

งานย่อย

1. ($20$ คะแนน) $N = 3$
2. ($20$ คะแนน) $A_i$ มีค่าเป็นหนึ่งใน $500, 800, 1000$ ($1 \le i \le N$)
3. ($20$ คะแนน) $A_i \ne A_j$ ($1 \le i < j \le N$)
4. ($40$ คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ข้อมูลนำเข้า

ข้อมูลนำเข้าจะถูกกำหนดให้ในรูปแบบต่อไปนี้:

N
A_1 A_2 ... A_N

ข้อมูลส่งออก

แสดงคะแนนต่ำสุดของนักเรียนในห้องเรียนพิเศษใน $1$ บรรทัด

ตัวอย่างข้อมูลนำเข้าและส่งออก

ตัวอย่างข้อมูลนำเข้า $1$

3
1000 500 800

ตัวอย่างข้อมูลส่งออก $1$

1000

ตัวอย่างเช่น หากกำหนดให้ $x = 900$ นักเรียนคนที่ $1$ จะถูกจัดให้อยู่ห้องเรียนพิเศษ และนักเรียนคนที่ $2, 3$ จะถูกจัดให้อยู่ห้องเรียนปกติ

อีกวิธีหนึ่งที่เป็นไปได้ในการแบ่งนักเรียนคือ จัดให้นักเรียนคนที่ $1, 3$ อยู่ห้องเรียนพิเศษ และนักเรียนคนที่ $2$ อยู่ห้องเรียนปกติ ซึ่งสามารถทำได้โดยกำหนดให้ $x = 800$ เป็นต้น

ทั้ง $2$ วิธีนี้มีผลต่างระหว่างจำนวนนักเรียนในห้องเรียนพิเศษกับห้องเรียนปกติเท่ากับ $1$ เหมือนกัน ดังนั้นจึงเลือกวิธีแรกซึ่งมีจำนวนนักเรียนในห้องเรียนพิเศษน้อยที่สุด ในกรณีนี้ คะแนนต่ำสุดของนักเรียนในห้องเรียนพิเศษคือ $1000$ คะแนน

ตัวอย่างข้อมูลนำเข้านี้สอดคล้องกับข้อจำกัดของงานย่อยทั้งหมด

ตัวอย่างข้อมูลนำเข้า $2$

6
100 75 41 75 13 89

ตัวอย่างข้อมูลส่งออก $2$

89

หากกำหนดให้ $x = 89$ นักเรียนคนที่ $1, 6$ จะถูกจัดให้อยู่ห้องเรียนพิเศษ และนักเรียนคนที่ $2, 3, 4, 5$ จะถูกจัดให้อยู่ห้องเรียนปกติ ในกรณีนี้ คะแนนต่ำสุดของนักเรียนในห้องเรียนพิเศษคือ $89$ คะแนน

ตัวอย่างข้อมูลนำเข้านี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $4$

ตัวอย่างข้อมูลนำเข้า $3$

6
20 25 12 7 13 16

ตัวอย่างข้อมูลส่งออก $3$

16

ตัวอย่างข้อมูลนำเข้านี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $3, 4$

ตัวอย่างข้อมูลนำเข้า $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

ตัวอย่างข้อมูลส่งออก $4$

364353982

ตัวอย่างข้อมูลนำเข้านี้สอดคล้องกับข้อจำกัดของงานย่อยที่ $4$