The median of an integer sequence can be found by arranging all the integers from the smallest to the largest and picking the middle one. If the number of integers is even, the median is defined to be the mean of the two middle integers. Given an integer sequence, output the median of the sequence.
There are multiple test cases. Each case begins with an integer N (1 <= N <= 106) in a line. The next line has N integers are in the next line, separated by spaces. The input is terminated if N = 0.
For each test case, print a number represent the median of the sequence.