תיאור הבעיה

בתיכון JOI יש בסך הכל $N$ תלמידי שכבה $1$, הממוספרים מ-$1$ עד $N$.

יום אחד, $N$ תלמידי שכבה $1$ ניגשו למבחן. הציון של תלמיד $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$.