Problembeskrivelse

Det er totalt $N$ elever på $1$. trinn ved JOI videregående skole, nummerert fra $1$ til $N$.

En dag tok de $N$ elevene på $1$. trinn en prøve. Poengsummen til elev $i$ ($1 \le i \le N$) var $A_i$ poeng. Her fikk ikke alle de $N$ elevene samme poengsum.

Basert på resultatene fra denne prøven bestemmes klasseinndelingen for neste skoleår. Mer presist velges et heltall $x$, og de $N$ elevene deles inn i $2$ klasser slik at elever med $x$ poeng eller mer kommer i fordypningsklassen, og elever med færre enn $x$ poeng kommer i ordinærklassen.

Her velges en inndeling slik at minst $1$ elev tilhører hver klasse, og slik at forskjellen mellom antallet elever i fordypningsklassen og antallet elever i ordinærklassen blir minst mulig. Hvis det finnes flere slike inndelinger, velges den blant dem som gir færrest elever i fordypningsklassen.

Gitt antallet elever og poengsummen til hver elev, skriv et program som finner den laveste poengsummen blant elevene i fordypningsklassen.

Begrensninger

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Det finnes $i, j$ ($1 \le i < j \le N$) slik at $A_i \ne A_j$.
• Alle inndataverdier er heltall.

Deloppgaver

1. ($20$ poeng) $N = 3$.
2. ($20$ poeng) $A_i$ er en av verdiene $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ poeng) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ poeng) Det er ingen ytterligere begrensninger.

Inndata

Inndata gis på følgende format:

N
A_1 A_2 ... A_N

Utdata

Skriv ut på $1$ linje den laveste poengsummen blant elevene i fordypningsklassen.

Eksempler på inndata og utdata

Eksempelinndata $1$

3
1000 500 800

Eksempelutdata $1$

1000

Hvis man for eksempel velger $x = 900$, plasseres elev $1$ i fordypningsklassen, og elevene $2, 3$ plasseres i ordinærklassen.

En annen mulig måte å dele inn elevene på er å plassere elevene $1, 3$ i fordypningsklassen og elev $2$ i ordinærklassen. Dette kan oppnås ved for eksempel å sette $x = 800$.

I begge disse $2$ inndelingene er forskjellen mellom antallet elever i fordypningsklassen og antallet elever i ordinærklassen lik $1$. Derfor velges den første inndelingen, som minimerer antallet elever i fordypningsklassen. Da er den laveste poengsummen blant elevene i fordypningsklassen $1000$ poeng.

Dette eksempelet oppfyller begrensningene i alle deloppgavene.

Eksempelinndata $2$

6
100 75 41 75 13 89

Eksempelutdata $2$

89

Hvis man setter $x = 89$, plasseres elevene $1, 6$ i fordypningsklassen og elevene $2, 3, 4, 5$ i ordinærklassen. Da er den laveste poengsummen blant elevene i fordypningsklassen $89$ poeng.

Dette eksempelet oppfyller begrensningene i deloppgave $4$.

Eksempelinndata $3$

6
20 25 12 7 13 16

Eksempelutdata $3$

16

Dette eksempelet oppfyller begrensningene i deloppgave $3, 4$.

Eksempelinndata $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Eksempelutdata $4$

364353982

Dette eksempelet oppfyller begrensningene i deloppgave $4$.