Problembeskrivning

Det går totalt $N$ elever i årskurs $1$ på JOI-gymnasiet, numrerade från $1$ till $N$.

En dag skrev de $N$ eleverna i årskurs $1$ ett prov. Resultatet för elev $i$ ($1 \le i \le N$) var $A_i$ poäng. Här fick inte alla $N$ elever samma poäng.

Utifrån resultaten på detta prov bestäms klassindelningen för nästa läsår. Mer specifikt väljs ett heltal $x$, och de $N$ eleverna delas in i $2$ klasser så att elever med minst $x$ poäng hamnar i spetsklassen och elever med färre än $x$ poäng hamnar i allmänklassen.

Här väljs en indelning så att minst $1$ elev tillhör varje klass och så att skillnaden mellan antalet elever i spetsklassen och antalet elever i allmänklassen blir så liten som möjligt. Om det finns flera sådana indelningar väljs bland dem den som minimerar antalet elever i spetsklassen.

Givet antalet elever och varje elevs poäng, skriv ett program som bestämmer den lägsta poängen bland eleverna i spetsklassen.

Begränsningar

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Det finns $i, j$ ($1 \le i < j \le N$) sådana att $A_i \ne A_j$.
• Alla indatavärden är heltal.

Deluppgifter

1. ($20$ poäng) $N = 3$.
2. ($20$ poäng) $A_i$ är något av $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ poäng) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ poäng) Det finns inga ytterligare begränsningar.

Indata

Indata ges i följande format:

N
A_1 A_2 ... A_N

Utdata

Skriv ut på $1$ rad den lägsta poängen bland eleverna i spetsklassen.

Exempel på indata och utdata

Exempelindata $1$

3
1000 500 800

Exempelutdata $1$

1000

Om man till exempel sätter $x = 900$ placeras elev $1$ i spetsklassen och eleverna $2, 3$ i allmänklassen.

Ett annat tänkbart sätt att dela in eleverna är att placera eleverna $1, 3$ i spetsklassen och elev $2$ i allmänklassen. Detta kan till exempel uppnås genom att sätta $x = 800$.

För båda dessa $2$ indelningar blir skillnaden mellan antalet elever i spetsklassen och antalet elever i allmänklassen $1$. Därför väljs den förstnämnda indelningen, som minimerar antalet elever i spetsklassen. Då är den lägsta poängen bland eleverna i spetsklassen $1000$ poäng.

Detta indataexempel uppfyller begränsningarna för alla deluppgifter.

Exempelindata $2$

6
100 75 41 75 13 89

Exempelutdata $2$

89

Om man sätter $x = 89$ placeras eleverna $1, 6$ i spetsklassen och eleverna $2, 3, 4, 5$ i allmänklassen. Då är den lägsta poängen bland eleverna i spetsklassen $89$ poäng.

Detta indataexempel uppfyller begränsningarna för deluppgift $4$.

Exempelindata $3$

6
20 25 12 7 13 16

Exempelutdata $3$

16

Detta indataexempel uppfyller begränsningarna för deluppgifterna $3, 4$.

Exempelindata $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Exempelutdata $4$

364353982

Detta indataexempel uppfyller begränsningarna för deluppgift $4$.