The median of a list of numbers is essentially its middle element after sorting.  The same number of elements occur after it as before.  Given a list of numbers with an odd number of elements, find the median?

Example 

$arr=[5,3,1,2,4]$   

The sorted array $ar r'=[1,2,3,4,5]$.  The middle element and the median is $3$.  

Function Description

Complete the findMedian function in the editor below.  

findMedian has the following parameter(s):  

int arr[n]: an unsorted array of integers  

Returns  

int: the median of the array

Input Format

The first line contains the integer $n$, the size of $\textbf{arr}$. 

The second line contains $n$ space-separated integers $arr\left[i\right]$

Constraints

$1\leq n\leq10000001$   
$n$ is odd
$-10000\leq arr[i]\leq10000$   

Sample Input 0
7
0 1 2 4 6 5 3

Sample Output 0
3

Explanation 0

The sorted $arr=[0,1,2,3,4,5,6]$.  It's middle element is at $ar r[3]=3$.

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
import math

def main():
	testcase = int(input())
	med = [int(i) for i in input().split()]
	print(findmed(med))

def findmed(med):
	med.sort()
	if len(med) % 2 == 1:
		return med[int(len(med) / 2)]
	else:
		return med[math.floor(len(med) / 2) + math.ceil(len(med) / 2)] / 2
main()


import random

def RSelect(a, n, order):
	i = 1
	pos = random.randrange(0, n)
	(a[0], a[pos]) = (a[pos], a[0])
	pivot = a[0]
	for j in range(1, n):
		if a[j] < pivot:
			(a[j], a[i]) = (a[i], a[j])
			i = i + 1
	(a[0], a[i - 1]) = (a[i - 1], a[0])
	if i == order:
		return pivot
	elif i > order:
		return RSelect(a[:i], len(a[:i]), order)
	elif i < order:
		return RSelect(a[i:], len(a[i:]), order - i)
n = int(input())
array = list(map(int, input().split()))
print(RSelect(array, n, int((n + 1) / 2)))


n = int(input())
ar = sorted(list(map(int, str(input()).split())))
m = int(n / 2)
print(ar[m])


n = int(input())
l = list(map(int, input().split()))
l.sort()
print(l[n >> 1])


def main():
	input()
	l = list(map(int, input().split()))
	l.sort()
	print(l[len(l) // 2])
main()


n = int(input())
ar = input().split()
ar = sorted(list(map(int, ar)))
mid = n // 2
print(ar[mid])


n = int(input())
a = sorted(map(int, input().split()))
print(a[n // 2])


numbers = int(input())
num_array = input()
num_array = num_array.split(' ')
i = 0
temp = 0
while i < numbers:
	num_array[i] = int(num_array[i])
	i += 1
num_array.sort()
if len(num_array) % 2 == 0:
	temp = len(num_array) / 2
	ans = num_array[temp] + num_array[temp - 1]
else:
	temp = int(len(num_array) / 2)
	ans = num_array[temp]
print(ans)


def median(a):
	a.sort()
	if len(a) % 2 == 1:
		return a[len(a) // 2]
	else:
		return (a[len(a) // 2] + a[len(a) // 2 - 1]) / 2
n = int(input())
a = [int(i) for i in input().split(' ')]
b = median(a)
print(b)


def median(n, l):
	l.sort()
	return l[n // 2]
a = int(input())
b = input().strip().split(' ')
c = []
for x in b:
	c.append(int(x))
print(median(a, c))


import sys

def main():
	N = int(sys.stdin.readline())
	ar = sorted([int(x) for x in sys.stdin.readline().split()])
	print(ar[len(ar) // 2])
main()


t = int(input())
ar = [int(i) for i in input().split()]
ar.sort()
print(ar[len(ar) // 2])


n = int(input())
a = input().split()
a = [int(b) for b in a]
a = sorted(a)
l = len(a)
if l % 2 == 0:
	print((a[l // 2] + a[l // 2 - 1]) / 2)
else:
	print(a[l // 2])


n = int(input())
rs = input().strip()
rs = list(map(int, rs.split(' ')))
rs.sort()
print(rs[int(n / 2)])


input()
nums = list(sorted(map(int, input().split())))
print(nums[len(nums) // 2])


def quickSelect(A, k):
	if len(A) == 1:
		return A[0]
	(p, L, R) = (A[0], [], [])
	for i in A:
		if i < p:
			L.append(i)
		if i > p:
			R.append(i)
	if len(L) > k:
		return quickSelect(L, k)
	elif len(L) == k:
		return p
	else:
		return quickSelect(R, k - len(L) - 1)
N = int(input())
ar = [int(x) for x in input().strip().split(' ')]
ar.sort()
print(ar[len(ar) // 2])


def main():
	N = int(input())
	med = int((N - 1) / 2)
	line = list(map(int, input().rstrip().split()))
	line = sorted(line)
	print(line[med])
	return 0
main()


def median(a, n):
	a = sorted(a)
	if n % 2 is 0:
		answer = (a[n / 2 - 1] + a[n // 2]) // 2
	else:
		answer = a[n // 2]
	return answer
n = int(input().strip())
b = input().strip()
b = list(map(int, b.split(' ')))
print(median(b, n))


def median(l, a):
	a = sorted(a)
	m = l // 2
	return a[m]
l = int(input().strip())
a = list(map(int, input().strip().split(' ')))
print(median(l, a))


input()
z = [int(i) for i in input().split()]
z.sort()
print(z[len(z) // 2])


length = int(input())
arr = [int(x) for x in input().split(' ')]
arr.sort()
print(arr[(length + 1) // 2 - 1])


def median(listin):
	listin.sort()
	m = listin[int(len(listin) / 2)]
	return m
l = input()
sample = list(map(int, input().split(' ')))
print(median(sample))


input()
arr = [int(n) for n in input().split()]
arr.sort()
print(arr[int(len(arr) / 2)])


sz = int(input())
ar = list(map(int, input().split(' ')))
ar.sort()
if sz % 2 == 0:
	print(ar[ceil(sz / 2)] + ar[floor(sz / 2)] / 2)
else:
	print(ar[int(sz / 2)])


n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
print(lst[int(len(lst) / 2)])


import sys
from heapq import nsmallest
raw_input = sys.stdin.readline
n = int(raw_input())
ar = raw_input().split(' ')
center = n // 2 + 1
print(nsmallest(center, (int(x) for x in ar))[-1])


N = int(input())
s = input()
s = s.split()
l = [int(x) for x in s]
l.sort()
if len(l) % 2 != 0:
	print(l[len(l) // 2])
else:
	m = (l[len(l)] + l[len(l) + 1]) / 2
	print(m)


import sys
n = int(sys.stdin.readline())
nums = [int(i) for i in sys.stdin.readline().split(' ')]
buckets = [0 for i in range(200)]
for i in nums:
	if i == 10000:
		buckets[199] = buckets[199] + 1
	else:
		buckets[int(i / 100 + 100)] = buckets[int(i / 100 + 100)] + 1
items = 0
bucket = 0
mindex = int((n - 1) / 2)
while bucket < 200:
	if items + buckets[bucket] > mindex:
		break
	items = items + buckets[bucket]
	bucket = bucket + 1
l = []
for i in nums:
	if int(i / 100 + 100) == bucket:
		l.append(i)
l.sort()
sys.stdout.write(str(l[mindex - items]))


def median(a):
	n = len(a)
	L = 0
	R = n - 1
	k = int(n / 2)
	while L < R:
		i = L
		j = R
		x = a[k]
		while i <= j:
			while a[i] < x:
				i += 1
			while j >= 0 and x < a[j]:
				j -= 1
			if i <= j:
				t = a[i]
				a[i] = a[j]
				a[j] = t
				i += 1
				j -= 1
		if j < k:
			L = i
		if k < i:
			R = j
	return a[k]
N = int(input())
l = [int(i) for i in str(input()).split()]
print(median(l))


import math
inpt = input()
inpt = int(inpt)
i = 0
array = ()
inpStr = input()
array = inpStr.split()
while i < inpt:
	array[i] = int(array[i])
	i = i + 1
array.sort()
print(array[int(inpt / 2)])


r = int(input())
s = input().split(' ')
for k in range(r):
	s[k] = int(s[k])
s.sort()
print(s[int((r - 1) / 2)])


b = input()
a = input().split(' ')
l = []
for i in range(int(b)):
	l.append(int(a[i]))
l.sort()
if len(l) % 2 == 0:
	med = (-1 + l[int(len(l) / 2)] + l[-1 + int(1 + len(l) / 2)]) / 2
else:
	med = l[int((len(l) - 1) / 2)]
print(med)


n = int(input())
ar = list(map(int, input().split()))
ar.sort()
print(ar[len(ar) // 2])


import sys

def partition(pivot, array):
	left = []
	right = []
	for element in array:
		if element < pivot:
			left.append(element)
		else:
			right.append(element)
	if len(left) >= 2:
		(left_left, right_left) = partition(left[0], left[1:])
		left_left.append(left[0])
		left = left_left + right_left
	if len(right) >= 2:
		(left_right, right_right) = partition(right[0], right[1:])
		left_right.append(right[0])
		right = left_right + right_right
	return (left, right)
numberOfElements = int(sys.stdin.readline())
elements = []
raw = sys.stdin.readline().split()
for index in range(numberOfElements):
	elements.append(int(raw[index]))
(left, right) = partition(elements[0], elements[1:])
left.append(elements[0])
left = left + right
print(left[(numberOfElements - 1) // 2])


n = int(input())
ar = sorted(map(int, input().split()))
print(ar[n // 2])


x = input()
z = input().split()
x = []
for i in z:
	i = int(i)
	x.append(i)
x.sort()
index = int((len(x) + 1) / 2)
median = x[index - 1]
print(median)


input()
a = sorted(map(int, input().split()))
print(a[len(a) // 2])


n = int(input())
ar = [int(v) for v in input().split()]

def partition(a, l, r):
	lp = l
	rp = lp
	while rp < r:
		if a[rp] < a[l]:
			lp += 1
			(a[rp], a[lp]) = (a[lp], a[rp])
		rp += 1
	if a[l] > a[lp]:
		(a[l], a[lp]) = (a[lp], a[l])
	return lp
(l, r) = (0, len(ar))
p = 0
index = len(ar) // 2
while r - l > 1:
	p = partition(ar, l, r)
	if p > index:
		r = p
	if p < index:
		l = p + 1
	if p == index:
		break
print(ar[index])


import sys

def main():
	n = int(sys.stdin.readline())
	lst = [int(i) for i in sys.stdin.readline().split()]
	lst.sort()
	print(lst[len(lst) // 2])
main()


N = int(input())
A = list(sorted(map(int, input().split())))
print(A[N // 2])


import sys
size = int(sys.stdin.readline().strip())
array = sorted([int(x) for x in sys.stdin.readline().split()])
if len(array) % 2 == 0:
	print(int(array[(len(array) - 1) // 2]))
else:
	print(int((array[(len(array) - 1) // 2] + array[len(array) // 2]) / 2))


import sys
import collections
n = int(input())
ar = [int(x) for x in input().split()]

def median(ar):
	ar.sort()
	if len(ar) % 2 == 0:
		return int((ar[len(ar) / 2] + ar[len(ar) / 2 - 1]) / 2)
	else:
		return ar[len(ar) // 2]
print(median(ar))


numItems = int(input())
array = [int(x) for x in input().split(' ')]
print(sorted(array)[len(array) // 2])


size = int(input())
n_list = []
n_str = str(input()).split()
for n in n_str:
	n_list.append(int(n))
n_list = sorted(n_list)
print(n_list[size // 2])


input()
ar = sorted((int(i) for i in input().split()))
print(ar[len(ar) // 2])


import sys

def kth(array, k):
	assert array
	less = list()
	greater = list()
	pivot = array.pop()
	for x in array:
		if x < pivot:
			less.append(x)
		else:
			greater.append(x)
	if len(less) == k - 1:
		return pivot
	elif len(less) >= k:
		return kth(less, k)
	else:
		return kth(greater, k - len(less) - 1)
N = int(sys.stdin.readline())
array = [int(X) for X in sys.stdin.readline().split()]
print(kth(array, len(array) // 2 + 1))


array_size = int(input())
array = [int(x) for x in input().split(' ')]
array.sort()
answer = array[array_size // 2:array_size // 2 + 1]
print(answer.pop())


def atindex(A, n):
	pivot = A[0]
	L = []
	R = []
	for a in A[1:]:
		if a < pivot:
			L.append(a)
		else:
			R.append(a)
	if len(L) >= n:
		return atindex(L, n)
	elif n > len(L) + 1:
		return atindex(R, n - len(L) - 1)
	else:
		return pivot
n = int(input())
ar = [int(e) for e in input().split()]
print(atindex(ar, int(len(ar) / 2) + 1))


n = int(input())
tab = sorted([int(i) for i in str(input()).split()])
print(tab[n // 2])


def solve(a, m):
	while a:
		p = a[0]
		b = [x for x in a if x < p]
		c = [x for x in a if x > p]
		if len(b) >= m:
			a = b
		elif len(b) + 1 == m:
			return p
		else:
			m -= len(b) + 1
			a = c
input()
a = [int(x) for x in input().split()]
m = len(a) // 2 + 1
a.sort()
print(a[m - 1])


import random

def partition(vector, left, right, pivotIndex):
	pivotValue = vector[pivotIndex]
	(vector[pivotIndex], vector[right]) = (vector[right], vector[pivotIndex])
	storeIndex = left
	for i in range(left, right):
		if vector[i] < pivotValue:
			(vector[storeIndex], vector[i]) = (vector[i], vector[storeIndex])
			storeIndex += 1
	(vector[right], vector[storeIndex]) = (vector[storeIndex], vector[right])
	return storeIndex

def _select(vector, left, right, k):
	while True:
		pivotIndex = random.randint(left, right)
		pivotNewIndex = partition(vector, left, right, pivotIndex)
		pivotDist = pivotNewIndex - left
		if pivotDist == k:
			return vector[pivotNewIndex]
		elif k < pivotDist:
			right = pivotNewIndex - 1
		else:
			k -= pivotDist + 1
			left = pivotNewIndex + 1

def select(vector, k, left=None, right=None):
	if left is None:
		left = 0
	lv1 = len(vector) - 1
	if right is None:
		right = lv1
	return _select(vector, left, right, k)
N = int(input())
arr = list(map(int, input().split()))
print(select(arr, int(N / 2)))


def prog(total):
	numbers = sorted([int(x) for x in str(input()).split()])
	print(numbers[int(len(numbers) / 2)])
prog(int(input()))


import fileinput, math
for line in fileinput.input():
	if fileinput.lineno() == 2:
		nums = line.split()
print(sorted(nums, key=int)[math.floor(len(nums) / 2)])


numberOfItems = int(input())
items = [int(x) for x in input().split()]
items.sort()
print(items[int(numberOfItems / 2)])


N = int(input())
array = list(map(int, input().split()))

def partition(array, pivot):
	I1 = []
	I2 = []
	I3 = []
	for elem in array:
		if elem < pivot:
			I1.append(elem)
		elif elem == pivot:
			I2.append(elem)
		else:
			I3.append(elem)
	return (I1, I2, I3)

def quickselect(array, n):
	if len(array) < 2:
		return array[n]
	pivot = array[0]
	(I1, I2, I3) = partition(array, pivot)
	if n < len(I1):
		return quickselect(I1, n)
	elif n < len(I1) + len(I2):
		return pivot
	else:
		return quickselect(I3, n - len(I1) - len(I2))
print(quickselect(array, len(array) // 2))


n = int(input())
nums = sorted([int(val) for val in input().split()])
l = len(nums)
if l % 2 == 1:
	print(nums[int(l / 2)])
else:
	a = l / 2
	b = l / 2 - 1
	print((nums[a] + nums[b]) / 2)


def swap(arr, i, j):
	if i != j:
		tmp = arr[i]
		arr[i] = arr[j]
		arr[j] = tmp

def findMedian(arr, start, end, M):
	if start == end:
		print(arr[start])
		return
	p = arr[start]
	r = start
	for i in range(start + 1, end + 1):
		if arr[i] < p:
			swap(arr, r + 1, i)
			r = r + 1
	swap(arr, start, r)
	if r == M:
		print(arr[r])
	elif r < M:
		findMedian(arr, r + 1, end, M)
	else:
		findMedian(arr, start, r - 1, M)
N = int(input())
arr = [int(x) for x in input().split()]
findMedian(arr, 0, N - 1, int(N / 2))


from sys import stdin

def median(ls):
	midpoint = len(ls) // 2
	if len(ls) % 2 == 1:
		return ls[midpoint]
	else:
		return (ls[midpoint - 1] + ls[midpoint + 1]) // 2
stdin.readline()
raw_list = [int(x) for x in stdin.readline().split()]
print(median(sorted(raw_list)))


import fileinput
import math

def median(array):
	return sorted(array)[math.floor(len(array) / 2)]
array = [int(x) for x in [line for line in fileinput.input()][1].split(' ')]
print(median(array))


n = int(input())
l = list(map(int, input().split()))
l.sort()
median = l[n // 2]
print(median)


n = int(input())
l = [int(x) for x in input().split()]
print(sorted(l)[n // 2])


x = int(input())
ns = list(map(int, input().split(' ')))
ns.sort()
l = len(ns)
if l % 2 != 0:
	print(ns[l // 2])
else:
	print(avg([ns[l // 2], ns[l // 2 - 1]]))


T = int(input())
arr = input().split()
arr = [int(arr[i]) for i in range(T)]
arr.sort()
print(arr[int(T / 2)])


n = int(input())
ar = [int(x) for x in input().split()]
ar.sort()
print(ar[len(ar) // 2])


def find_nth(array, n):
	pivot = array[0]
	left = [a for a in array[1:] if a <= pivot]
	if len(left) >= n:
		return find_nth(left, n)
	elif len(left) + 1 == n:
		return pivot
	else:
		right = [a for a in array[1:] if a > pivot]
		return find_nth(right, n - len(left) - 1)

def find_median(array):
	return find_nth(array, len(array) // 2 + 1)
array_size = int(input())
array = list(map(int, input().split(' ')))
median = find_median(array)
print(median)


n = int(input())
arrTemp = input().split()
arr = [int(x) for x in arrTemp]
arr.sort()
print(arr[n // 2])


n = int(input())
v = list(map(int, input().split()))
v.sort()
print(v[int(n / 2)])


n = int(input())
a = sorted(map(int, input().split()))
print(a[n // 2])


from math import ceil
from random import randint

def quick_select(lst, k):
	while len(lst) > 1:
		left = []
		right = []
		index = randint(0, len(lst) - 1)
		pivot = lst.pop(index)
		for num in lst:
			if num <= pivot:
				left.append(num)
			else:
				right.append(num)
		m = len(left)
		if m > k:
			lst = left
		else:
			lst = [pivot] + right
			k -= m
	else:
		return lst[0]
n = int(input())
lst = [int(x) for x in input().strip().split()]
print(quick_select(lst, n // 2))


_ = input()
print(sorted([int(x) for x in input().split(' ')])[int(_) // 2])


n = int(input())
ar = [int(x) for x in input().split(' ')]

def nth_find(start_pos, n, end_pos):
	if start_pos == n and end_pos == start_pos + 1:
		print(ar[n])
		return
	pivot = ar[end_pos - 1]
	left_edge = start_pos
	for i in range(start_pos, end_pos):
		if ar[i] < pivot:
			(ar[left_edge], ar[i]) = (ar[i], ar[left_edge])
			left_edge += 1
	(ar[left_edge], ar[end_pos - 1]) = (ar[end_pos - 1], ar[left_edge])
	if left_edge == n:
		print(ar[left_edge])
		return
	if left_edge > n:
		return nth_find(start_pos, n, left_edge)
	else:
		return nth_find(left_edge + 1, n, end_pos)
nth_find(0, (len(ar) - 1) // 2, len(ar))


(n, ar, lst) = (int(input()), input(), [])
for i in ar.split():
	lst.append(int(i))
lst.sort()
print(lst[int((len(lst) - 1) / 2)])


def makelistsameline(strnos):
	return list(map(lambda x: int(x), strnos.split()))

def pp(L):
	print(' '.join(map(str, L)))
N = int(input())
ar = makelistsameline(input())
count = dict.fromkeys(range(-10000, 10000), 0)
for x in ar:
	count[x] += 1
ordered = []
for (no, times) in tuple(count.items()):
	if times == 0:
		continue
	ordered.extend([no] * times)
x = len(ordered) // 2
print(ordered[x])


n = int(input())
data = [int(x) for x in input().split()]

def partition(data, low, high):
	pivot = data[high]
	pivot_index = low - 1
	for index in range(low, high):
		if data[index] <= pivot:
			pivot_index += 1
			(data[index], data[pivot_index]) = (data[pivot_index], data[index])
	pivot_index += 1
	(data[pivot_index], data[high]) = (data[high], data[pivot_index])
	return pivot_index

def quick_sort(data, low, high, median_index):
	if low < high:
		pivot_index = partition(data, low, high)
		quick_sort(data, low, pivot_index - 1, median_index)
		quick_sort(data, pivot_index + 1, high, median_index)
quick_sort(data, 0, n - 1, n // 2)
print(data[n // 2])


from statistics import median
n = eval(input())
a = list(map(int, input().split()))
print(median(a))


length = int(input())
array = sorted(list(map(int, input().strip().split(' '))))
if not length % 2:
	print((array[int(length / 2)] + array[int(length / 2 - 1)]) / 2)
else:
	print(array[int(length / 2)])


input()
l = list(map(int, input().split()))
l.sort()
print(l[len(l) // 2])


n = int(input())
nbs = sorted([int(i) for i in input().split()])
print(nbs[n // 2])


n = int(input())
array = list(map(int, input().split()))
array.sort()
print(array[n // 2])


_ = input()
v = list(map(int, input().split()))
print(sorted(v)[len(v) // 2])


from statistics import median
n = int(input())
array = list(map(int, input().split(' ')))
print(int(median(array)))


j = input()
a = []
a = input().split()
a = [int(s) for s in a]
a = sorted(a)
l = len(a)
if l % 2 == 0:
	print(a[int(l / 2 - 1)])
else:
	print(a[int((l + 1) / 2 - 1)])


__author__ = 'danielbaeck'
import math
import itertools
n = input()
numbers = [int(x) for x in input().split(' ')]
numbers.sort()
print(numbers[int(len(numbers) / 2)])


def median(arr):
	return find(arr, len(arr) // 2, 0, len(arr) - 1)

def find(arr, k, l, r):
	p = partition(arr, l, r)
	if p < k:
		return find(arr, k, p + 1, r)
	elif p > k:
		return find(arr, k, 0, p - 1)
	else:
		return arr[p]

def partition(arr, l, r):
	k = l + (r - l) // 2
	v = arr[k]
	swap(arr, k, r)
	ins = l
	for i in range(l, r):
		if arr[i] < v:
			swap(arr, i, ins)
			ins += 1
	swap(arr, r, ins)
	return ins

def swap(arr, a, b):
	(arr[a], arr[b]) = (arr[b], arr[a])
n = int(input())
arr = [int(x) for x in input().split()]
print(median(arr))


a = int(input())
b = []
c = []
r = str(input()).split(' ')
b.append(r)
for i in range(a):
	c.append(int(b[0][i]))
c.sort()
if len(c) % 2 == 1:
	print(c[len(c) // 2])
else:
	print(c[len(c) / 2], c[len(c) / 2 + 1])


input()
arr = sorted(list(map(int, input().split())))
mid = int(len(arr) / 2)
print(arr[mid])


size = int(input())
arr = input().split(' ')
for each in range(len(arr)):
	arr[each] = int(arr[each])
arr.sort()
print(arr[int((len(arr) - 1) / 2)])


import statistics
input()
a = map(int, input().split())
print(statistics.median(a))


def median(array, i, j):
	if j - i == 0:
		return array[i]
	if j - i == 1:
		return (array[j] + array[i]) / 2
	left = median(array, i, i + (j - i) // 3)
	med = median(array, i + (j - i) // 3 + 1, i + 2 * (j - i) // 3)
	right = median(array, i + 2 * (j - i) // 3 + 1, j)
	print(i, j, left, med, right)
	if left <= med and left >= right or (left <= right and left >= med):
		return left
	elif med <= left and med >= right or (med <= right and med >= left):
		return med
	else:
		return right
n = int(input())
array = list(map(int, input().split()))
array.sort()
if n % 2 == 0:
	print((array[n // 2] + array[n // 2 + 1]) / 2)
else:
	print(array[n // 2])


import random

def partition(lst, start, end):
	(i, j) = (start + 1, end)
	while True:
		while i < end and lst[i] <= lst[start]:
			i += 1
		while j > start and lst[j] >= lst[start]:
			j -= 1
		if i >= j:
			break
		(lst[i], lst[j]) = (lst[j], lst[i])
	(lst[start], lst[j]) = (lst[j], lst[start])
	return j

def find_kth(lst, k):
	random.shuffle(lst)
	(start, end) = (0, len(lst) - 1)
	while start < end:
		mid = partition(lst, start, end)
		if mid == k:
			return lst[mid]
		elif mid < k:
			start = mid + 1
		else:
			end = mid - 1
	return lst[k]

def find_median(lst):
	return find_kth(lst, len(lst) // 2)
_ = input()
lst = [int(el) for el in input().strip().split()]
print(find_median(lst))


N = eval(input())
ar = list(input().split(' '))
ar = [int(i) for i in ar]
ar = sorted(ar)
print(ar[len(ar) // 2])


def find_k(vector, k):
	pivot = vector[-1]
	less = []
	greater = []
	for el in vector[:-1]:
		if el <= pivot:
			less.append(el)
		else:
			greater.append(el)
	if len(less) + 1 == k:
		return pivot
	elif len(less) + 1 > k:
		return find_k(less, k)
	else:
		return find_k(greater, k - len(less) - 1)
import math
N = int(input())
median = math.ceil(N / 2)
vector = [int(el) for el in input().split()]
print(find_k(vector, median))


n = int(input())
ar = sorted([int(i) for i in str(input()).split()])
if n % 2:
	print(ar[n // 2])
else:
	print((ar[n // 2 - 1] + ar[n // 2]) / 2)


def median(A):
	n = len(A)
	A = sorted(A)
	if n == 1:
		med = A[0]
	elif n % 2 == 0:
		med = (A[n // 2 - 1] + A[n // 2]) // 2
	else:
		med = A[(n + 1) // 2 - 1]
	print(med)
numberOfElements = int(input())
if 1 <= numberOfElements <= 1000001:
	inputList = input()
	inputArray = inputList.split()
	for i in range(len(inputArray)):
		inputArray[i] = int(inputArray[i])
	if numberOfElements == len(inputArray):
		median(inputArray)


n = int(input())
l = [int(x) for x in input().split()]
l.sort()
if n % 2 == 1:
	print(l[int(len(l) / 2)])
else:
	print((l[int(len(l) / 2) - 1] + l[int(len(l) / 2)]) / 2)


n = int(input().strip())
A = [int(i) for i in input().split()]
A = sorted(A)
if len(A) % 2 == 1:
	print(A[len(A) // 2])
else:
	print(A[len(A) // 2])


l = eval(input())
arr = list(map(int, input().split(' ')))
arr.sort()
if l % 2 == 0:
	print((arr[l // 2] + arr[l // 2 - 1]) // 2)
else:
	print(arr[l // 2])


N = int(input())
ar = [int(i) for i in input().split()]
ar = sorted(ar)
print(ar[(N - 1) // 2])