Testo del problema

Gli studenti del $1$° anno del liceo JOI sono in totale $N$, numerati da $1$ a $N$.

Un giorno, gli $N$ studenti del $1$° anno hanno sostenuto un esame. Il punteggio dello studente $i$ ($1 \le i \le N$) è stato di $A_i$ punti. Non tutti gli $N$ studenti hanno ottenuto lo stesso punteggio.

In base ai risultati di questo esame viene determinata la suddivisione in classi per il prossimo anno scolastico. Nello specifico, viene scelto un intero $x$ e gli $N$ studenti vengono divisi in $2$ classi in modo che gli studenti con un punteggio maggiore o uguale a $x$ punti vadano nella Classe Avanzata e quelli con un punteggio inferiore a $x$ punti vadano nella Classe Ordinaria.

Viene scelta una suddivisione tale che a ciascuna classe appartenga almeno $1$ studente e che la differenza tra il numero di studenti della Classe Avanzata e il numero di studenti della Classe Ordinaria sia minima. Inoltre, se ci sono più suddivisioni di questo tipo, viene scelta tra esse quella che rende minimo il numero di studenti nella Classe Avanzata.

Dato il numero di studenti e il punteggio di ciascuno studente, scrivi un programma che trovi il punteggio minimo tra gli studenti della Classe Avanzata.

Vincoli

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Esistono $i, j$ ($1 \le i < j \le N$) tali che $A_i \ne A_j$.
• Tutti i valori in input sono numeri interi.

Sottoproblemi

1. ($20$ punti) $N = 3$.
2. ($20$ punti) $A_i$ è uno tra $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ punti) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ punti) Non ci sono vincoli aggiuntivi.

Input

L'input è fornito nel seguente formato:

N
A_1 A_2 ... A_N

Output

Stampa su $1$ riga il punteggio minimo tra gli studenti della Classe Avanzata.

Esempi di Input e Output

Esempio di Input $1$

3
1000 500 800

Esempio di Output $1$

1000

Ad esempio, ponendo $x = 900$, lo studente $1$ viene assegnato alla Classe Avanzata e gli studenti $2, 3$ alla Classe Ordinaria.

Un'altra possibile suddivisione degli studenti consiste nell'assegnare gli studenti $1, 3$ alla Classe Avanzata e lo studente $2$ alla Classe Ordinaria. Ciò può essere ottenuto ad esempio ponendo $x = 800$.

In entrambe queste $2$ suddivisioni, la differenza tra il numero di studenti della Classe Avanzata e quello della Classe Ordinaria è $1$. Pertanto viene scelta la prima suddivisione, che minimizza il numero di studenti nella Classe Avanzata. In tal caso, il punteggio minimo tra gli studenti della Classe Avanzata è $1000$ punti.

Questo esempio di input soddisfa i vincoli di tutti i sottoproblemi.

Esempio di Input $2$

6
100 75 41 75 13 89

Esempio di Output $2$

89

Ponendo $x = 89$, gli studenti $1, 6$ vengono assegnati alla Classe Avanzata e gli studenti $2, 3, 4, 5$ alla Classe Ordinaria. In tal caso il punteggio minimo tra gli studenti della Classe Avanzata è $89$ punti.

Questo esempio di input soddisfa i vincoli del Sottoproblema $4$.

Esempio di Input $3$

6
20 25 12 7 13 16

Esempio di Output $3$

16

Questo esempio di input soddisfa i vincoli dei Sottoproblemi $3, 4$.

Esempio di Input $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Esempio di Output $4$

364353982

Questo esempio di input soddisfa i vincoli del Sottoproblema $4$.