Treść zadania

W Liceum JOI jest łącznie $N$ uczniów $1$. klasy, ponumerowanych od $1$ do $N$.

Pewnego dnia $N$ uczniów $1$. klasy przystąpiło do egzaminu. Wynik ucznia $i$ ($1 \le i \le N$) wyniósł $A_i$ punktów. Przy czym nie wszyscy spośród $N$ uczniów uzyskali taki sam wynik.

Na podstawie wyników tego egzaminu ustalany jest podział na klasy na kolejny rok szkolny. Dokładniej, wybierana jest pewna liczba całkowita $x$ i $N$ uczniów dzieli się na $2$ klasy w taki sposób, że uczniowie z wynikiem co najmniej $x$ punktów trafiają do klasy rozszerzonej, a uczniowie z wynikiem poniżej $x$ punktów trafiają do klasy ogólnej.

Wybierany jest taki podział, w którym do każdej klasy należy co najmniej $1$ uczeń, a różnica między liczbą uczniów w klasie rozszerzonej i liczbą uczniów w klasie ogólnej jest jak najmniejsza. Co więcej, jeśli istnieje wiele takich podziałów, wybierany jest spośród nich ten, w którym liczba uczniów w klasie rozszerzonej jest najmniejsza.

Mając daną liczbę uczniów oraz wyniki poszczególnych uczniów, napisz program wyznaczający najniższy wynik spośród uczniów klasy rozszerzonej.

Ograniczenia

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Istnieją takie $i, j$ ($1 \le i < j \le N$), że $A_i \ne A_j$.
• Wszystkie wartości wejściowe są liczbami całkowitymi.

Podzadania

1. ($20$ punktów) $N = 3$.
2. ($20$ punktów) $A_i$ jest jedną z liczb $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ punktów) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ punktów) Brak dodatkowych ograniczeń.

Wejście

Wejście podawane jest w następującym formacie:

N
A_1 A_2 ... A_N

Wyjście

Wypisz w $1$ wierszu najniższy wynik spośród uczniów klasy rozszerzonej.

Przykłady wejścia i wyjścia

Przykładowe wejście $1$

3
1000 500 800

Przykładowe wyjście $1$

1000

Na przykład dla $x = 900$ uczeń $1$ trafia do klasy rozszerzonej, a uczniowie $2, 3$ do klasy ogólnej.

Innym możliwym podziałem uczniów jest przydzielenie uczniów $1, 3$ do klasy rozszerzonej, a ucznia $2$ do klasy ogólnej. Można to uzyskać np. przyjmując $x = 800$.

W obu tych $2$ podziałach różnica między liczbą uczniów w klasie rozszerzonej a liczbą uczniów w klasie ogólnej wynosi $1$. Wybierany jest zatem pierwszy podział, który minimalizuje liczbę uczniów w klasie rozszerzonej. Wówczas najniższy wynik w klasie rozszerzonej wynosi $1000$ punktów.

Ten przykład wejścia spełnia ograniczenia wszystkich podzadań.

Przykładowe wejście $2$

6
100 75 41 75 13 89

Przykładowe wyjście $2$

89

Dla $x = 89$ uczniowie $1, 6$ trafiają do klasy rozszerzonej, a uczniowie $2, 3, 4, 5$ do klasy ogólnej. Wówczas najniższy wynik w klasie rozszerzonej wynosi $89$ punktów.

Ten przykład wejścia spełnia ograniczenia podzadania $4$.

Przykładowe wejście $3$

6
20 25 12 7 13 16

Przykładowe wyjście $3$

16

Ten przykład wejścia spełnia ograniczenia podzadań $3, 4$.

Przykładowe wejście $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Przykładowe wyjście $4$

364353982

Ten przykład wejścia spełnia ograniczenia podzadania $4$.