Cho dãy số nguyên ~ a_1, a_2, … , a_n ~. Hãy tìm giá trị của phần tử trung vị của dãy số. Biết rằng phần tử trung vị của một dãy số là phần tử nằm chính giữa dãy số sau khi sắp xếp.

Ví dụ dãy ~ 3, 4, 2, 1, 5 ~ sau khi sắp xếp ~ 1, 2, 3, 4, 5 ~ nên ~ 3 ~ là giá trị cần tìm

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ n ~ ~ (1 ≤ n ≤ 2.10^6; n ~ lẻ ~ ) ~
• Dòng thứ hai ghi lần lượt các số ~ a_1 , a_2, … ,a_n ~. ~ (|a_i | ≤ 10^9) ~

Kết quả

Một số nguyên duy nhất là giá trị tìm được.

Ví dụ:

Input 1

5
3 4 2 1 5 

Output 1

3