Есептің шарты

JOI жоғары мектебінде $1$-ден $N$-ге дейін нөмірленген барлығы $N$ $1$-сынып оқушысы бар.

Бір күні $1$-сыныптың $N$ оқушысы емтихан тапсырды. $i$-ші оқушының ($1 \le i \le N$) ұпайы $A_i$ ұпай болды. Мұнда $N$ оқушының барлығы бірдей ұпай алған жоқ.

Осы емтихан нәтижесі бойынша келесі оқу жылындағы сыныптарға бөлу анықталады. Нақтырақ айтқанда, белгілі бір $x$ бүтін саны таңдалып, ұпайы кемінде $x$ ұпай болған оқушылар бейіндік сыныпқа, ал ұпайы $x$ ұпайдан төмен болған оқушылар қарапайым сыныпқа баратындай етіп $N$ оқушы $2$ сыныпқа бөлінеді.

Бұл ретте әр сыныпта кемінде $1$ оқушы болатындай және бейіндік сыныптағы оқушылар саны мен қарапайым сыныптағы оқушылар санының айырмасы ең аз болатындай бөлу тәсілі таңдалады. Оның үстіне, егер мұндай бөлу тәсілдері бірнешеу болса, олардың ішінен бейіндік сыныптағы оқушылар саны ең аз болатын бөлу тәсілі таңдалады.

Оқушылар саны мен әр оқушының ұпайы берілген кезде, бейіндік сыныптағы оқушылардың ең төменгі ұпайын табатын программа жазыңыз.

Шектеулер

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• $A_i \ne A_j$ болатындай $i, j$ ($1 \le i < j \le N$) бар.
• Енгізілетін барлық мәндер бүтін сандар болып табылады.

Ішкі есептер

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$-ші ішкі есептің шектеулерін қанағаттандырады.