Given an array \(A\) of \(N\) integers, find the median of \(A\). Recall that the median is the middle value of the set of numbers when they are in order.

If there are two middle values, output their average rounded down to the nearest integer.

Constraints

\(1 \le N \le 10 ^ 4\)

\(1 \le A_{i} \le 10 ^ 4\)

Input Specification

The first line will consist of one integer \(N\), representing the size of the array

The following N lines will consist of an integer \(A_{i}\), representing the value of index \(i\) in the array.

Output Specification

Output the median of the array, rounded down to the nearest integer.

Sample Input 1

5
3
2
6
1
5

Sample Output 1

3

Sample Input 2

6
1
30
25
15
21
18

Sample Output 2

19

Explanation for Sample Output 2

When in order, \(A\) becomes \([1, 15, 18, 21, 25, 30]\). The median is betweeen 18 and 21, which averages out to 19.5. Since we round down to the nearest integer, we just output 19.