نص المسألة

يوجد في مدرسة JOI الثانوية إجمالي $N$ من طلاب السنة $1$، مرقمين من $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$.