Cho một dãy số gồm \(n\) số nguyên. Phần tử trung vị là phần tử mà sau khi dãy số được sắp xếp tăng dần, nó nằm chính giữa dãy nếu \(n\) là số lẻ.

Yêu cầu: Tìm giá trị của phần tử trung vị.

Input

• Dòng đầu chứa số nguyên lẻ \(n\) \((1 \le n \le 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) với \(|a_i| \le 10^9\).

Output

In ra một dòng duy nhất là phần tử trung vị của dãy.

Sample Input

5
1 5 7 2 9

Sample Output

5

Subtask

• 30%: \(n \le 100\)
• 30%: \(n \le 5000\)
• 40%: Không có ràng buộc bổ sung