Verkefnislýsing

Á $1$. ári í JOI-menntaskólanum eru alls $N$ nemendur, númeraðir frá $1$ til $N$.

Dag einn tóku allir $N$ nemendurnir á $1$. ári próf. Einkunn nemanda $i$ ($1 \le i \le N$) var $A_i$ stig. Hér fengu ekki allir $N$ nemendurnir sömu einkunn.

Bekkjaskiptingin fyrir næsta skólaár ræðst af niðurstöðum þessa prófs. Nánar tiltekið er valin heiltala $x$ og $N$ nemendunum skipt í $2$ bekki þannig að nemendur með $x$ stig eðaป meira fara í framhaldsbekk en nemendur með færri en $x$ stig fara í almennan bekk.

Hér er valin skipting þannig að að minnsta kosti $1$ nemandi sé í hvorum bekk og munurinn á fjölda nemenda í framhaldsbekknum og fjölda nemenda í almenna bekknum sé sem minnstur. Ef fleiri en ein slík skipting kemur til greina er valin sú þeirra þar sem fjöldi nemenda í framhaldsbekknum er sem minnstur.

Gefinn er fjöldi nemenda og einkunn hvers nemanda. Skrifaðu forrit sem finnur lægstu einkunnina meðal nemenda í framhaldsbekknum.

Takmarkanir

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Til eru $i, j$ ($1 \le i < j \le N$) þannig að $A_i \ne A_j$.
• Öll inntaksgildi eru heiltölur.

Undirverkefni

1. ($20$ stig) $N = 3$.
2. ($20$ stig) $A_i$ er eitt af gildunum $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ stig) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ stig) Engar frekari takmarkanir.

Inntak

Inntakið er gefið á eftirfarandi sniði:

N
A_1 A_2 ... A_N

Úttak

Prentaðu í $1$ línu lægstu einkunnina meðal nemenda í framhaldsbekknum.

Dæmi um inntak og úttak

Dæmi um inntak $1$

3
1000 500 800

Dæmi um úttak $1$

1000

Til dæmis, ef $x = 900$ fer nemandi $1$ í framhaldsbekkinn og nemendur $2, 3$ fara í almenna bekkinn.

Önnur möguleg skipting nemendanna er að setja nemendur $1, 3$ í framhaldsbekkinn og nemanda $2$ í almenna bekkinn. Því má til dæmis ná með því að velja $x = 800$.

Í báðum þessum $2$ skiptingum er munurinn á fjölda nemenda í framhaldsbekknum og almenna bekknum $1$. Því er fyrri skiptingin valin, þar sem hún lágmarkar fjölda nemenda í framhaldsbekknum. Þá er lægsta einkunnin meðal nemenda í framhaldsbekknum $1000$ stig.

Þetta inntaksdæmi uppfyllir takmarkanir allra undirverkefna.

Dæmi um inntak $2$

6
100 75 41 75 13 89

Dæmi um úttak $2$

89

Ef $x = 89$ fara nemendur $1, 6$ í framhaldsbekkinn og nemendur $2, 3, 4, 5$ í almenna bekkinn. Þá er lægsta einkunnin meðal nemenda í framhaldsbekknum $89$ stig.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefnis $4$.

Dæmi um inntak $3$

6
20 25 12 7 13 16

Dæmi um úttak $3$

16

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $3, 4$.

Dæmi um inntak $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Dæmi um úttak $4$

364353982

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefnis $4$.