Lower Median

Difficulty: 1000 3000 ms 128 MB

sorting

Print the lower median: the element at position ⌈N/2⌉ when the values are sorted (1-based).

Input: the first line has N; the second line has N integers.

Output: the lower median.

Constraints:

• 1 ≤ N ≤ 10⁵
• −10⁹ ≤ a_i ≤ 10⁹

Sample Tests

5
7 1 5 9 3

5

4
4 1 3 2

2

Read the Editorial