Đề bài

Khối lớp $1$ của trường Trung học phổ thông JOI có tổng cộng $N$ học sinh, được đánh số từ $1$ đến $N$.

Một ngày nọ, $N$ học sinh khối $1$ tham gia một kỳ thi. Điểm số của học sinh $i$ ($1 \le i \le N$) là $A_i$ điểm. Ở đây, không phải tất cả $N$ học sinh đều đạt cùng một số điểm.

Dựa vào kết quả của kỳ thi này, việc phân lớp cho năm học tới sẽ được quyết định. Cụ thể, người ta chọn một số nguyên $x$, và chia $N$ học sinh thành $2$ lớp sao cho những học sinh có điểm số từ $x$ điểm trở lên sẽ vào Lớp Chọn, còn những học sinh có điểm số dưới $x$ điểm sẽ vào Lớp Thường.

Ở đây, cách chia được chọn sao cho mỗi lớp có ít nhất $1$ học sinh, đồng thời độ chênh lệch giữa số học sinh của Lớp Chọn và số học sinh của Lớp Thường là nhỏ nhất. Hơn nữa, nếu có nhiều cách chia như vậy, người ta sẽ chọn cách chia có số lượng học sinh trong Lớp Chọn là nhỏ nhất.

Cho biết số lượng học sinh và điểm số của từng học sinh, hãy viết chương trình tìm điểm số thấp nhất trong số các học sinh thuộc Lớp Chọn.

Giới hạn

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Tồn tại $i, j$ ($1 \le i < j \le N$) sao cho $A_i \ne A_j$.
• Tất cả các giá trị đầu vào đều là số nguyên.

Subtask

1. ($20$ điểm) $N = 3$.
2. ($20$ điểm) $A_i$ là một trong các giá trị $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ điểm) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ điểm) Không có giới hạn bổ sung.

Dữ liệu vào

Dữ liệu vào được cung cấp theo định dạng sau:

N
A_1 A_2 ... A_N

Kết quả ra

In ra trên $1$ dòng điểm số thấp nhất của học sinh trong Lớp Chọn.

Ví dụ

Dữ liệu vào mẫu $1$

3
1000 500 800

Kết quả ra mẫu $1$

1000

Ví dụ, nếu chọn $x = 900$, học sinh $1$ được xếp vào Lớp Chọn, còn học sinh $2, 3$ được xếp vào Lớp Thường.

Một cách chia học sinh khác có thể nghĩ tới là xếp học sinh $1, 3$ vào Lớp Chọn và học sinh $2$ vào Lớp Thường. Điều này có thể thực hiện được bằng cách chọn $x = 800$.

Cả $2$ cách chia này đều có độ chênh lệch giữa số học sinh Lớp Chọn và số học sinh Lớp Thường là $1$. Do đó, cách chia thứ nhất có số học sinh Lớp Chọn nhỏ nhất sẽ được chọn. Khi đó, điểm số thấp nhất của học sinh trong Lớp Chọn là $1000$ điểm.

Ví dụ này thỏa mãn giới hạn của tất cả các subtask.

Dữ liệu vào mẫu $2$

6
100 75 41 75 13 89

Kết quả ra mẫu $2$

89

Nếu chọn $x = 89$, học sinh $1, 6$ được xếp vào Lớp Chọn, và học sinh $2, 3, 4, 5$ được xếp vào Lớp Thường. Khi đó điểm số thấp nhất của học sinh trong Lớp Chọn là $89$ điểm.

Ví dụ này thỏa mãn giới hạn của Subtask $4$.

Dữ liệu vào mẫu $3$

6
20 25 12 7 13 16

Kết quả ra mẫu $3$

16

Ví dụ này thỏa mãn giới hạn của Subtask $3, 4$.

Dữ liệu vào mẫu $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Kết quả ra mẫu $4$

364353982

Ví dụ này thỏa mãn giới hạn của Subtask $4$.