Deskripsi Masalah

Terdapat total $N$ siswa kelas $1$ di SMA JOI, yang diberi nomor dari $1$ hingga $N$.

Suatu hari, $N$ siswa kelas $1$ tersebut mengikuti ujian. Skor siswa $i$ ($1 \le i \le N$) adalah $A_i$ poin. Di sini, tidak semua $N$ siswa mendapatkan skor yang sama.

Berdasarkan hasil ujian ini, pembagian kelas untuk tahun ajaran berikutnya ditentukan. Secara spesifik, sebuah bilangan bulat $x$ dipilih, lalu $N$ siswa dibagi menjadi $2$ kelas sedemikian rupa sehingga siswa dengan skor $x$ poin atau lebih masuk ke Kelas Unggulan, dan siswa dengan skor kurang dari $x$ poin masuk ke Kelas Reguler.

Di sini, pembagian dipilih sedemikian rupa sehingga masing-masing kelas memiliki setidaknya $1$ siswa, dan selisih antara banyaknya siswa di Kelas Unggulan dan banyaknya siswa di Kelas Reguler menjadi sekecil mungkin. Lebih lanjut, jika terdapat beberapa pembagian semacam itu, dipilih pembagian di antaranya yang meminimalkan banyaknya siswa di Kelas Unggulan.

Diberikan banyaknya siswa dan skor masing-masing siswa, buatlah program untuk mencari skor terendah di antara siswa-siswa di Kelas Unggulan.

Batasan

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Terdapat $i, j$ ($1 \le i < j \le N$) sehingga $A_i \ne A_j$.
• Semua nilai masukan adalah bilangan bulat.

Subsoal

1. ($20$ poin) $N = 3$.
2. ($20$ poin) $A_i$ adalah salah satu dari $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ poin) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ poin) Tidak ada batasan tambahan.

Masukan

Masukan diberikan dalam format berikut:

N
A_1 A_2 ... A_N

Keluaran

Keluarkan skor terendah di antara siswa di Kelas Unggulan dalam $1$ baris.

Contoh Masukan dan Keluaran

Contoh Masukan $1$

3
1000 500 800

Contoh Keluaran $1$

1000

Sebagai contoh, jika $x = 900$, siswa $1$ ditempatkan di Kelas Unggulan, dan siswa $2, 3$ ditempatkan di Kelas Reguler.

Cara pembagian siswa lain yang mungkin adalah menempatkan siswa $1, 3$ di Kelas Unggulan dan siswa $2$ di Kelas Reguler. Hal ini dapat dicapai misalnya dengan memilih $x = 800$.

Pada kedua ($2$) cara pembagian ini, selisih antara banyaknya siswa di Kelas Unggulan dan banyaknya siswa di Kelas Reguler sama-sama $1$. Oleh karena itu, dipilih pembagian pertama yang meminimalkan banyaknya siswa di Kelas Unggulan. Pada saat ini, skor terendah di antara siswa di Kelas Unggulan adalah $1000$ poin.

Contoh masukan ini memenuhi batasan semua subsoal.

Contoh Masukan $2$

6
100 75 41 75 13 89

Contoh Keluaran $2$

89

Jika $x = 89$, siswa $1, 6$ ditempatkan di Kelas Unggulan, dan siswa $2, 3, 4, 5$ ditempatkan di Kelas Reguler. Pada saat ini, skor terendah di antara siswa di Kelas Unggulan adalah $89$ poin.

Contoh masukan ini memenuhi batasan Subsoal $4$.

Contoh Masukan $3$

6
20 25 12 7 13 16

Contoh Keluaran $3$

16

Contoh masukan ini memenuhi batasan Subsoal $3, 4$.

Contoh Masukan $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Contoh Keluaran $4$

364353982

Contoh masukan ini memenuhi batasan Subsoal $4$.