Bình muốn tìm số trung vị của mảng gồm \(N\) số nguyên. Số trung vị là số nằm ở vị trí chính giữa sau khi mảng đã được sắp xếp tăng dần. Nếu mảng có số lượng phần tử chẵn, ta chọn phần tử ở vị trí chính giữa làm tròn dưới (tức là tại chỉ số \(N/2\) nếu đánh số từ 0).

Hãy viết chương trình giúp Bình!

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) cách nhau bởi dấu cách (\(-10^9 \le A_i \le 10^9\)).

Dữ liệu ra

• In ra một số nguyên duy nhất là số trung vị tìm được.

Ví dụ 1

Đầu vào:

5
3 1 5 4 2

Đầu ra:

3

Giải thích: Sau khi sắp xếp: 1, 2, 3, 4, 5. Số ở giữa là 3.

Ví dụ 2

Đầu vào:

4
1 4 2 3

Đầu ra:

3

Giải thích: Sau khi sắp xếp: 1, 2, 3, 4. Chỉ số \(4/2 = 2\) (0-indexed) tương ứng với số 3.