You are given n points on a line with their coordinates x_{i}. Find the point x so the sum of distances to the given points is minimal.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5) — the number of points on the line.

The second line contains n integers x_{i} ( - 10^9 ≤ x_{i} ≤ 10^9) — the coordinates of the given n points.


-----Output-----

Print the only integer x — the position of the optimal point on the line. If there are several optimal points print the position of the leftmost one. It is guaranteed that the answer is always the integer.


-----Example-----
Input
4
1 2 3 4

Output
2

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Complete search


Solutions:
n = int(input())
s = list(map(int, input().strip().split()))
s.sort()
print(s[int(n / 2) - 1] if n % 2 == 0 else s[int(n / 2)])


N = int(input())
number_list = list(map(int, input().split(' ')))
number_list.sort()
mid = len(number_list) // 2
if len(number_list) % 2 == 0:
	median = (number_list[mid - 1] + number_list[mid]) / 2.0
else:
	median = number_list[mid]
min_value = min((abs(i - median) for i in number_list))
temp = []
for j in number_list:
	if abs(j - median) == min_value:
		temp.append(j)
print(temp[0])


from collections import Counter
from fractions import gcd
from functools import reduce
from math import acos, ceil, cos, floor, pi, sin, sqrt
from random import random
from string import ascii_lowercase, ascii_uppercase, digits
from sys import exit, setrecursionlimit, stdin
setrecursionlimit(10 ** 7)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
mod = int(1000000000.0 + 7)
eps = 1e-06
MAX = 10 ** 10
n = int(input())
x = sorted(list(map(int, input().split())))
print(x[(n - 1) // 2])


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


n = int(input())
a = list(map(int, input().strip().split(' ')))
a = sorted(a)
print(a[int((n - 1) / 2)])


n = int(input())
m = [int(x) for x in input().split()]
m.sort()
print(m[(n - 1) // 2])


n = int(input())
coo = [int(i) for i in input().split(' ')]
coo.sort()
print(coo[(n - 1) // 2])


n = int(input())
ms = [int(i) for i in input().split()]
ms.sort()
if n % 2 == 1:
	print(ms[n // 2])
else:
	print(ms[n // 2 - 1])


n = int(input())
x_list = list(map(int, input().split()))
x_list.sort()
i = n + 1 >> 1 if n & 1 else n >> 1
print(x_list[i - 1])


n = int(input())
a = list(map(int, input().split()))
a.sort()
if n % 2 == 0:
	print(a[n // 2 - 1])
else:
	print(a[n // 2])


n = int(input())
x = sorted(list(map(int, input().split())))
(P, N) = (0, 0)
a = n * [0]
for i in range(1, n):
	P = (x[i] - x[i - 1]) * i + P
	N = (x[-i] - x[-i - 1]) * i + N
	a[i] += P
	a[-i - 1] += N
print(x[a.index(min(a))])


N = int(input())
numbers = [int(n) for n in input().split()]
numbers.sort()
if N % 2 == 1:
	Ans = numbers[N // 2]
	print(Ans)
else:
	Ans = numbers[N // 2 - 1]
	print(Ans)


def abs(x):
	if x < 0:
		return -x
	else:
		return x
inp = input()
n = int(inp)
x = input().split()
for i in range(0, n):
	x[i] = int(x[i])
x.sort()
ans = 0
val = 0
for i in range(0, n):
	val += x[i] - x[0]
ans = val
pnt = x[0]
diff = 0
for i in range(1, n):
	diff = x[i] - x[i - 1]
	val -= diff * (n - i)
	val += diff * i
	if ans > val:
		pnt = x[i]
		ans = val
print(pnt)


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


n = int(input())
arr = [int(i) for i in input().split()]
arr.sort()
if n % 2 == 0:
	print(arr[n // 2 - 1])
else:
	print(arr[n // 2])


import statistics
n = int(input())
list1 = input().split()
list1 = list(map(int, list1))
if len(list1) % 2 == 1:
	print(statistics.median(list1))
else:
	list1.remove(max(list1))
	print(statistics.median(list1))


n = int(input())
L = list(map(int, input().split()))
L.sort()
if n % 2 == 0:
	ans = n // 2 - 1
else:
	ans = n // 2
print(L[ans])


a = int(input())
x = sorted(list(map(int, input().split())))
print(x[(a + 1) // 2 - 1])


import math
n = int(input())
ls = list(map(int, input().split()))
ls.sort()
if n % 2 == 0:
	print(ls[n // 2 - 1])
else:
	print(ls[n // 2])


n = int(input())
points = list(map(int, input().split()))
points = sorted(points)
mid = n // 2 + n % 2 - 1
print(points[mid])


n = int(input())
X = [int(x) for x in input().split()]
X.sort()
lrdiff = n
cur = X[0]
for x in X:
	if lrdiff > 0:
		cur = x
		lrdiff -= 2
		continue
	break
print(cur)


def d(a, x):
	t = 0
	for n in a:
		t += abs(n - x)
	return t

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n % 2 == 0:
		if d(a, a[n // 2 - 1]) <= d(a, a[n // 2]):
			print(a[n // 2 - 1])
		else:
			print(a[n // 2])
	else:
		print(a[n // 2])

def main():
	solve()

def __starting_point():
	main()
__starting_point()


n = int(input())
x = [int(val) for val in input().split()]
x.sort()
print(x[(n - 1) // 2])


import sys
from statistics import median
from math import floor
sys.stdin.readline()
numbers = sorted((int(a) for a in sys.stdin.readline().split()))
print(numbers[floor((len(numbers) - 1) / 2)])


n = int(input())
l = input().split(' ')
p = [int(x) for x in l]
p.sort()
if n & 1 == 0:
	ans = n // 2 - 1
else:
	ans = n // 2
print(p[ans])


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


import sys
input = sys.stdin.readline
n = int(input())
points = list(map(int, input().strip().split()))
points.sort()
if n % 2 == 1:
	n = n // 2
else:
	n = n // 2 - 1
print(points[n])


def main():
	n = int(input())
	arr = [int(a) for a in input().split()]
	arr.sort()
	print(arr[len(arr) // 2 - 1 + len(arr) % 2])
main()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	n = int(inp())
	a = lis()
	a = sorted(a)
	print(a[n // 2 if n % 2 == 1 else n // 2 - 1])
testcase(1)


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


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


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


from sys import stdin
n = int(stdin.readline())
points = sorted((int(x) for x in stdin.readline().split()))
if n % 2 == 0:
	print(points[n // 2 - 1])
else:
	print(points[n // 2])


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


n = int(input())
li = list(map(int, input().split()))[:n]
li.sort()
if n % 2 == 0:
	m = n // 2 - 1
else:
	m = n // 2
print(li[m])


n = int(input())
x = list(map(int, input().split()))
x.sort()
print(x[int((n + 1) / 2) - 1])


numPoints = int(input())
points = list(map(int, input().split(' ')))
points.sort()

def calcVal(point, points):
	tally = 0
	for i in range(len(points)):
		tally += abs(points[i] - point)
	return tally
if len(points) % 2 == 0:
	leftDex = len(points) // 2 - 1
	rightDex = len(points) // 2
	print(points[leftDex])
else:
	index = len(points) // 2
	print(points[index])


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


import unittest
from random import randint, shuffle
from sys import maxsize

class StressTest(unittest.TestCase):
	known_values = (([1, 2, 3, 4], 2),)

	def test_known_cases(self):
		for (A, expected) in self.known_values:
			self.assertEqual(expected, BestSolution().optimalPoint(A))

	def test_all_cases(self):
		while True:
			break

class NaiveSolution:

	def optimalPoint(self, A):
		A.sort()
		mean = sum(A) / len(A)
		dist = maxsize
		ret = None
		for a in A:
			if abs(a - mean) > dist:
				break
			dist = abs(a - mean)
			ret = a
		return ret

class BestSolution:

	def optimalPoint(self, A):
		A.sort()
		mid = (len(A) - 1) // 2
		return A[mid]
input()
A = [int(x) for x in input().strip().split()]
print(BestSolution().optimalPoint(A))


import sys
from math import floor, gcd, factorial
input = sys.stdin.readline

def printf(x, end='\n'):
	sys.stdout.write(str(x) + end)

def main():
	T = 1

	def solve():
		n = int(input())
		arr = list(map(int, input().split()))
		arr.sort()
		if n % 2 == 1:
			print(arr[n // 2])
		else:
			print(arr[n // 2 - 1])
	for i in range(T):
		solve()
	pass
main()


n = int(input())
array = list(map(int, input().split()))
array.sort()
summ = sum(array)
summ2 = 0
differences = [0] * n
for i in range(n):
	differences[i] = summ - (summ2 + array[i]) - summ2
	summ2 += array[i]
dist = [0] * n
for i in range(n):
	dist[i] = array[i] * i + differences[i] - array[i] * (n - i - 1)
minId = 0
for i in range(n):
	if dist[i] < dist[minId]:
		minId = i
print(array[minId])


n = int(input())
x = [int(s) for s in input().split()]
x.sort()
print(x[(n - 1) // 2])


count = int(input())
nums = sorted([int(num) for num in input().split()])
print(nums[(count - 1) // 2])


n = int(input())
numbers = list(map(int, input().split()))
numbers.sort()
numbers
print(numbers[(n + 1) // 2 - 1])


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


n = int(input())
l = sorted(list(map(int, input().split())))
h = len(l)
if h % 2 == 0:
	h = int(h / 2 - 1)
else:
	h = int(h // 2)
print(l[h])


from sys import stdin, stdout

def right_range(x):
	return cntr[-1] - cntr[x] - (coordinate[x] - coordinate[0]) * (n - x - 1)

def left_range(x):
	return cntl[0] - cntl[x] - (coordinate[-1] - coordinate[x]) * x
n = int(stdin.readline())
coordinate = sorted(list(map(int, stdin.readline().split())))
cntr = [0]
cntl = [0]
for i in range(1, n):
	cntr.append(cntr[-1] + coordinate[i] - coordinate[0])
for i in range(n - 2, -1, -1):
	cntl.append(cntl[-1] + coordinate[-1] - coordinate[i])
cntl = cntl[::-1]
ind = 0
for i in range(n):
	if right_range(ind) + left_range(ind) > right_range(i) + left_range(i):
		ind = i
stdout.write(str(coordinate[ind]))


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


n = int(input())
a = list(map(int, input().split()))
a.sort()
k = 0
r = 0
for i in range(1, n):
	k = k + abs(a[i] - a[0])
if n % 2 == 1:
	print(a[n // 2])
else:
	for j in range(n):
		r = r + abs(a[n // 2 - 1] - a[j])
	for i in range(n):
		k = k + abs(a[n // 2] - a[i])
	if r <= k:
		print(a[n // 2 - 1])
	else:
		print(a[n // 2])


input()
(lambda x: print(x[(len(x) - 1) // 2]))(list(sorted([int(x) for x in input().split()])))


n = int(input())
X = list(map(int, input().split()))
X.sort()
print(X[(n + 1) // 2 - 1])


n = int(input())
a = input().split(' ')
a = sorted([int(i) for i in a])
print(a[int((n - 1) / 2)])


n = int(input())
a = sorted(map(int, input().split()))
print(a[n // 2 - (1 if n & 1 == 0 else 0)])


import math

class CodeforcesTask710BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.numbers = []

	def read_input(self):
		self.n = int(input())
		self.numbers = [int(x) for x in input().split(' ')]

	def process_task(self):
		self.numbers.sort()
		if self.n % 2:
			self.result = self.numbers[self.n // 2]
		else:
			self.result = self.numbers[self.n // 2 - 1]

	def get_result(self):
		return self.result
Solution = CodeforcesTask710BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


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


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0

def hnbhai(tc):
	n = sb()
	a = sd()
	a.sort()
	mid = n // 2 - 1 + n % 2
	print(a[mid])
for _ in range(1):
	hnbhai(_ + 1)


n = int(input())
arr = sorted(list(map(int, input().split())))
if len(arr) % 2 == 0:
	print(arr[len(arr) // 2 - 1])
else:
	print(arr[len(arr) // 2])


n = int(input())
points = sorted(tuple(map(int, input().split())))

def calc(points, start, stop, step):
	n = len(points)
	ans = [None] * n
	ans[start] = 0
	cnt = 1
	for i in range(start + step, stop, step):
		ans[i] = ans[i - step] + abs(points[i] - points[i - step]) * cnt
		cnt += 1
	return ans
calc1 = calc(points, 0, n, 1)
calc2 = calc(points, n - 1, -1, -1)
(mini, minv) = (-1, float('inf'))
for i in range(n):
	if calc1[i] + calc2[i] < minv:
		minv = calc1[i] + calc2[i]
		mini = points[i]
print(mini)


import math
n = int(input())
ar = sorted([int(x) for x in input().split()])
ind = math.ceil(len(ar) / 2)
print(ar[ind - 1])


import sys
INF = 10 ** 9 + 3
fin = sys.stdin
fout = sys.stdout
n = int(fin.readline())
points = list(map(int, fin.readline().split()))
points.sort()
if n % 2 == 1:
	fout.write(str(points[n // 2]))
else:
	fout.write(str(points[n // 2 - 1]))


from collections import defaultdict
import sys
n = int(input())
index = list(map(int, input().split()))
index.sort()
print(index[(n - 1) // 2])


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


import heapq

def heapsort(iterable):
	h = []
	for value in iterable:
		heapq.heappush(h, value)
	return [heapq.heappop(h) for i in range(len(h))]
a = int(input())
b = list(map(int, input().split(' ')))
b = heapsort(b)
if a % 2 == 1:
	print(b[a // 2])
else:
	print(b[a // 2 - 1])


__author__ = 'Think'
n = int(input())
points = sorted([int(i) for i in input().split()])
print(points[(n - 1) // 2])


n = int(input())
l = list(map(int, input().strip().split(' ')))
l.sort()
a = {0: 'even', 1: 'odd'}
s = sum(l)
if a[n % 2] is 'even':
	n -= 1
	sum1 = 0
	for k in l:
		sum1 += abs(k - l[int(n / 2)])
	sum2 = 0
	for k in l:
		sum2 += abs(k - l[int((n + 1) / 2)])
	if sum1 > sum2:
		print(l[int((n + 1) / 2)])
	else:
		print(l[int(n / 2)])
else:
	n -= 1
	print(l[int(n / 2)])


n = int(input())
numbers = [int(n) for n in input().split()]
ns = sorted(numbers)
print(ns[(n - 1) // 2])


n = int(input())
nums = list(map(int, input().split()))
nums = sorted(nums)
if n % 2 == 0:
	print(nums[int(n / 2) - 1])
else:
	print(nums[n // 2])


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
print(arr[(1 + n) // 2 - 1])


import io
import sys
import time
import random
n = int(input())
x = [int(x) for x in input().split()]
x.sort()
if len(x) % 2 == 0:
	print(x[(len(x) - 1) // 2])
else:
	print(x[len(x) // 2])


import os
import sys
debug = True
if debug and os.path.exists('input.in'):
	input = open('input.in', 'r').readline
else:
	debug = False
	input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_count = 1
N = inp()
A = inlt()
A.sort()
sum = []
for i in range(N):
	if i == 0:
		sum.append(A[0])
	else:
		sum.append(sum[i - 1] + A[i])
sum.append(sum[N - 1])
min_total = -1
min_x = -1
for i in range(N):
	total = i * A[i] - (0 if i == 0 else sum[i - 1]) + (sum[N] - sum[i]) - (N - i - 1) * A[i]
	if min_total == -1 or total < min_total:
		min_total = total
		min_x = A[i]
print(min_x)


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


a = int(input())
b = [int(i) for i in input().split()]
b.sort()
if a % 2 == 0:
	print(b[a // 2 - 1])
else:
	print(b[a // 2])


import sys
input = sys.stdin.readline

def ceil(x, y):
	return (x + y - 1) // y

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(10000000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

def int_array():
	return list(map(int, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
n = int(input())
a = sorted(int_array())
if n & 1:
	print(a[n // 2])
else:
	x = a[n // 2 - 1]
	y = a[n // 2]
	ans1 = ans2 = 0
	for i in a:
		ans1 += abs(x - i)
		ans2 += abs(y - i)
	if ans1 <= ans2:
		print(x)
	else:
		print(y)


def get_median(data, n):
	data.sort()
	return data[int((n + 1) / 2) - 1]

def main():
	n = int(input())
	nNumsLine = list(map(int, input().split()))
	print(int(get_median(nNumsLine, n)))
main()


def main():
	n = int(input())
	points = [int(x) for x in input().split()]
	points.sort()
	print(points[(n - 1) // 2])
main()


import math
n = int(input())
string = input()
numbers = sorted(map(int, string.split()))
print(numbers[math.ceil(n / 2) - 1])


n = int(input())
points = sorted(map(lambda x: int(x), input().split()))
print(points[n // 2 + n % 2 - 1])


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


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
print(a[(n - 1) // 2])


n = int(input())
A = sorted([int(x) for x in input().split()])
print(A[(len(A) - 1) // 2])


n = int(input())
x = [int(y) for y in input().split()]
x.sort()
print(x[(n - 1) // 2])


from math import *
num = int(input())
pra = input()
psp = pra.split(' ')
q = []
for i in psp:
	j = int(i)
	q.append(j)
res = sorted(q)
pos = floor((num + 1) / 2) - 1
print(res[pos])


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


n = int(input())
pos = [int(x) for x in input().split()]
pos.sort()
print(pos[(n - 1) // 2])


N = int(input())
X = list(map(int, input().split()))
X.sort()
if N % 2 != 0:
	print(X[N // 2])
else:
	left = sum([abs(x - X[N // 2 - 1]) for x in X])
	right = sum([abs(x - X[N // 2]) for x in X])
	if left <= right:
		print(X[N // 2 - 1])
	elif left > right:
		print(X[N // 2])


n = int(input())
x = [int(p) for p in input().split()]
x.sort()
S = [0]
for i in range(0, n):
	S.append(S[i] + x[i])
L = []
R = []
for i in range(0, n):
	L.append(i * x[i] - S[i])
	R.append(S[n] - S[i + 1] - (n - i - 1) * x[i])
mind = L[0] + R[0]
mini = 0
for i in range(1, n):
	d = L[i] + R[i]
	if d < mind:
		(mind, mini) = (d, i)
print(x[mini])


n = int(input())
l = list(map(int, input().split()))
l.sort()
x = n // 2
if n % 2 == 0:
	x -= 1
print(l[x])


n = int(input())
dots = [int(x) for x in input().split()]
dots.sort()
dot = dots[0]
left = 0
right = sum([abs(x - dot) for x in dots])
results = [right]
for i in range(1, n):
	ldot = dot
	dot = dots[i]
	left += (dot - ldot) * i
	right -= (dot - ldot) * (n - i)
	results.append(left + right)
print(dots[results.index(min(results))])


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


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return fac

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
a = sorted(list(map(int, input().split())))
if n % 2 != 0:
	c = n // 2
	print(a[c])
else:
	c1 = a[n // 2]
	c2 = a[n // 2 - 1]
	sum1 = 0
	sum2 = 0
	for i in range(0, len(a)):
		sum1 += abs(c1 - a[i])
		sum2 += abs(c2 - a[i])
	if sum1 >= sum2:
		print(c2)
	else:
		print(c1)


import sys
input = sys.stdin.readline
n = int(input())
seq = sorted([int(i) for i in input().split()])
print(seq[(n - 1) // 2])


a = int(input())
b = sorted(list(map(int, input().split())))
print(b[(a - 1) // 2])


n = int(input())
l = list(map(int, input().split()))
l.sort()
ls = [0 for i in range(1, n + 1)]
ls[0] = l[0]
for i in range(1, n):
	ls[i] = l[i] + ls[i - 1]
dis = 10 ** 15 * 4
ans = 10 ** 15
for i in range(0, n):
	x = l[i] * (i + 1) - l[i] * (n - (i + 1)) - ls[i] + ls[-1] - ls[i]
	if x < dis:
		dis = x
		ans = l[i]
print(ans)


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


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n = ii()
l = sorted(il())
print(l[(n - 1) // 2])


import io
import os
import sys
from random import randint
from atexit import register
DEBUG = False
STRESSTEST = False
if not DEBUG:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = io.BytesIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
tokens = []
tokens_next = 0

def nextStr():
	global tokens, tokens_next
	while tokens_next >= len(tokens):
		tokens = input().split()
		tokens_next = 0
	tokens_next += 1
	if type(tokens[tokens_next - 1]) == str:
		return tokens[tokens_next - 1]
	return tokens[tokens_next - 1].decode()

def nextInt():
	return int(nextStr())

def nextIntArr(n):
	return [nextInt() for i in range(n)]

def print(*argv, end='\n'):
	for arg in argv:
		sys.stdout.write((str(arg) + ' ').encode())
	sys.stdout.write(end.encode())

def genTestCase():
	N = 3
	V = 10 ** 3
	n = randint(1, N)
	return [randint(-V, V) for i in range(n)]

def bruteforce(a):
	best = (10 ** 100, -1)
	for i in range(min(a), max(a) + 1):
		cur = sum((abs(j - i) for j in a))
		if cur < best[0]:
			best = (cur, i)
	return best[1]

def doStressTest():
	while True:
		curTest = genTestCase()
		mySoln = solve(curTest)
		bruteforceSoln = bruteforce(curTest)
		if mySoln != bruteforceSoln:
			print('### Found case ###')
			print(curTest)
			print(f'{mySoln} should have been: {bruteforceSoln}')
			return

def solve1(a):
	a = sorted(a)
	sumLeft = 0
	sumRight = sum((i - a[0] for i in a[1:]))
	best = (sumLeft + sumRight, a[0])
	for i in range(1, len(a)):
		dis = a[i] - a[i - 1]
		sumLeft += dis * i
		sumRight -= dis * (len(a) - i)
		if sumLeft + sumRight < best[0]:
			best = (sumLeft + sumRight, a[i])
	return best[1]
from functools import cmp_to_key

def cmp(a, b):
	if a[1] != b[1]:
		return a[1] - b[1]
	return a[0] - b[0]

def solve2(a):
	a = sorted(a)
	median = len(a) // 2
	indices = range(max(0, median - 10), min(median + 11, len(a)))
	t = map(lambda x: a[x], indices)
	t = map(lambda x: sum((abs(j - x) for j in a)), t)
	t = zip(indices, t)
	t = sorted(t, key=cmp_to_key(cmp))
	return a[t[0][0]]

def solve3(a):
	if len(a) < 2:
		return a[0]
	avg = sum(a) / len(a)
	closest = sorted(a, key=lambda x: abs(x - avg))[:2]
	t = map(lambda x: sum((abs(j - x) for j in a)), closest)
	t = list(t)
	if t[0] == t[1]:
		return sorted(closest, key=lambda x: a.index(x))[0]
	return closest[0] if t[0] < t[1] else closest[1]

def solve(a):
	return solve1(a)
if not DEBUG and STRESSTEST:
	raise Exception('Wrong flags!')
if STRESSTEST:
	doStressTest()
else:
	a = nextIntArr(nextInt())
	res = solve(a)
	print(res)
sys.stdout.flush()


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


import sys
input = sys.stdin.readline
n = int(input())
k = list(map(int, input().split()))
k.sort()
print(k[(n - 1) // 2])


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
if n % 2 == 1:
	print(l[n // 2])
else:
	k1 = l[n // 2]
	k2 = l[n // 2 - 1]
	(d1, d2) = (0, 0)
	for i in range(n):
		d1 += abs(l[i] - k1)
	for i in range(n):
		d2 += abs(l[i] - k2)
	if d1 < d2:
		print(k1)
	else:
		print(k2)


import sys
sys.setrecursionlimit(30000)
from collections import Counter, defaultdict, deque
from math import ceil, floor, factorial, fsum, isinf, exp, log, log10, log2, isfinite, sqrt
from math import pi as PI, e as E
from fractions import Fraction
from itertools import starmap, tee, chain, filterfalse, combinations as combos
from itertools import permutations as perms, product as prod, combinations_with_replacement as rcombos
from functools import reduce, partial
import operator as ops
from operator import __not__ as notit
from operator import __abs__ as absit
from operator import __or__ as orit
(PHI, PHI2) = ((1 + 5 ** 0.5) / 2, (5 ** 0.5 - 1) / 2)
INF = float('inf')

class TreeNode:

	def __init__(self, v):
		self.val = v
		self.left = None
		self.right = None

def setBit(x, offset):
	return x | 1 << offset

def clearBit(x, offset):
	return x & ~(1 << offset)

def getBit(x, offset):
	return 1 if testBit(x, offset) > 0 else 0

def testBit(x, offset):
	return x & 1 << offset

def flipBitAt(x, offset):
	return x ^ 1 << offset

def flipBits(x, length=-1):
	length = x.bit_length() - 1 if length == -1 else length
	return x ^ (1 << length) - 1

def numBits(x):
	return x.bit_length()

def countOnes(x):
	return bin(x).count('1')

def countZeros(x, length=-1):
	length = x.bit_length() if length == -1 else length
	return length - countOnes(x)

def getList(tcast=str):
	return [tcast(x) for x in input().strip().split(' ')]

def getItems(*tcast):
	return map(lambda f, x: f(x), tcast, getList())

def getVal(tcast=str):
	return tcast(input().strip())

def getMatrix(r, tcast=str):
	return [getList(tcast) for row in range(r)]

def isOdd(n):
	return n & 1 > 0

def isEven(n):
	return not n & 1

def numDigits(n):
	return len(str(n)) - (1 if n < 0 else 0)

def getRecip(f):
	return Fraction(f.denominator, f.numerator)

def _gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def gcd(*xs):
	nums = xs[0] if type(xs[0]) == list else list(xs)
	cur = nums[0]
	for n in nums[1:]:
		if cur == 1:
			return cur
		cur = _gcd(cur, n)
	return cur

def _lcm(a, b):
	return a // gcd(a, b) * b

def lcm(*xs):
	nums = xs[0] if type(xs[0]) == list else list(xs)
	cur = nums[0]
	for n in nums[1:]:
		cur = _lcm(cur, n)
	return cur

def primesUpto(n):
	isp = [True] * (n + 1)
	(isp[0], isp[1]) = (False, False)
	primes = []
	for (i, x) in enumerate(isp):
		if x:
			primes.append(i)
			mults = i * i
			while mults <= n:
				isp[mults] = False
				mults += i
	return primes

def primeFactor(n):
	factors = Counter()
	while not n & 1:
		factors[2] += 1
		n >>= 1
	trynum = 3
	while trynum <= ceil(sqrt(n)):
		while n % trynum == 0:
			factors[trynum] += 1
			n //= trynum
		trynum += 2
	if n != 1:
		factors[n] += 1
	return factors

def isPrime(n):
	if n & 1 and n >= 2:
		trynum = 3
		limit = ceil(sqrt(n))
		while trynum < limit:
			if n % trynum == 0:
				return False
			trynum += 2
		else:
			return True
	else:
		return False

def nthFib(n):
	if n <= 2:
		return 1
	else:
		(a, b) = (1, 1)
		while n > 2:
			(a, b) = (b, a + b)
			n -= 1
		return b

def zipNWith(f, *x):
	return (f(y) for y in zip(*x))

def zipWith(f, xs, ys):
	return (f(x, y) for (x, y) in zip(xs, ys))

def flatten(xs):
	return reduce(ops.concat, xs)

def quantify(pred, it):
	return sum(map(pred, it))

def dotproduct(xs, ys):
	return sum(map(ops.mul, xs, ys))

def pairwise(it):
	(a, b) = tee(it)
	next(b, None)
	return zip(a, b)

def bipartition(pred, it):
	(t, f) = tee(it)
	return (filter(pred, t), filterfalse(pred, f))

def powerset(it):
	s = list(it)
	return chain.from_iterable((combos(s, r) for r in range(len(s) + 1)))
n = getVal(int)
nums = getList(int)
nums.sort()
mid = (n - 1) // 2
print(nums[mid])


import math
x = int(input())
a = list(map(int, input().split()))
a.sort()
y = int(math.floor(x / 2))
if x % 2 == 0:
	print(a[y - 1], end='')
else:
	print(a[y], end='')


n = int(input())
x = list(map(int, input().split()))
x.sort()
s = sum(x)
it = x[0]
m = s - n * x[0]
result = x[0]
for i in range(1, n):
	cur = s - it - (n - i) * x[i] + (i * x[i] - it)
	it += x[i]
	if cur < m:
		result = x[i]
		m = cur
print(result)


n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
print(lst[int(n / 2 + 0.5) - 1])


n = int(input())
x = sorted(list(map(int, input().split())))
print(x[int((len(x) - 0.5) / 2)])


try:
	while True:
		n = int(input())
		a = sorted(map(int, input().split()))
		ls = 0
		result = rs = sum(a) - a[0] * n
		index = 0
		for i in range(1, n):
			d = a[i] - a[i - 1]
			ls += d * i
			rs -= d * (n - i)
			if ls + rs < result:
				result = ls + rs
				index = i
		print(a[index])
except EOFError:
	pass


def main():
	n = int(input())
	arr = map(int, str(input()).split())
	arr = list(sorted(arr))
	if n % 2 == 0:
		n = int(n / 2)
	else:
		n = int(n / 2 + 1)
	print(arr[n - 1])
main()


n = int(input())
ls = sorted(list(map(int, input().split())))
if n & 1 == 0:
	ans = n // 2 - 1
else:
	ans = n // 2
print(ls[ans])


import math
import re
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
print(arr[math.ceil(n / 2) - 1])


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


import sys
n = int(input())
str = input()
a = [int(x) for x in str.split()]
a.sort()
print(a[(n - 1) // 2])


n = int(input())
x = [int(q) for q in input().split()]
x = sorted(x)
if n & 1 == 0:
	print(x[n // 2 - 1])
else:
	print(x[n // 2])


n = int(input())
dist = 0
dict = {}
change = -n + 2
lst = list(map(int, input().split()))
lst.sort()
n = 0
i1 = lst[0]
ret = lst[0]
for i in lst[1:]:
	if change >= 0:
		break
	dist += change * (i - i1)
	ret = i
	n = dist
	change += 2
	i1 = i
print(ret)


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


n = int(input())
a = list(map(int, input().split()))
print(sorted(a)[n - 1 >> 1])


n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
l = [0] * 333333
r = [0] * 333333
for i in range(1, n):
	l[i] = l[i - 1] + i * (a[i] - a[i - 1])
for i in range(n - 2, -1, -1):
	r[i] = r[i + 1] + (n - i - 1) * (a[i + 1] - a[i])
mn = 2222222222222222
ind = 0
for i in range(n):
	if mn > l[i] + r[i]:
		mn = l[i] + r[i]
		ind = i
print(a[ind])


from sys import stdin
n = int(input())
arr = list(map(int, stdin.readline().split()))
arr.sort()
m = int(n / 2)
if n % 2 == 0:
	print(arr[m - 1])
else:
	print(arr[m])


import sys
from math import *
n = int(input())
a = list(map(int, input().split()))
a.sort()
print(a[int((n - 1) / 2)])


import math
n = int(input())
T = input()
num = [int(x) for x in T.split()]
num.sort()
p = math.ceil(n / 2)
print(num[p - 1])


from sys import stdin
n = int(input())
points = list(map(int, stdin.readline().split()))
points.sort()
indice = n // 2
if n % 2 == 0 and n != 0:
	indice -= 1
print(points[indice])


n = int(input())
s = input().split()
for i in range(n):
	s[i] = int(s[i])
s.sort()
if n % 2 != 0:
	print(s[n // 2])
else:
	print(s[n // 2 - 1])


n = int(input())
line = sorted(list(map(int, input().split())))
a = 0
for i in range(1, n):
	a += line[i] - line[0]
ind = line[0]
rasst = a
for i in range(1, n):
	r = abs(line[i] - line[i - 1])
	a1 = a - (n - i - 1) * r + (i - 1) * r
	if a1 < rasst:
		rasst = a1
		ind = line[i]
	a = a1
print(ind)


def main():
	n = int(input())
	print(sorted(map(int, input().split()))[(n - 1) // 2])
main()


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


read = input().split(' ')
n = int(read[0])
tab = sorted(map(int, input().split(' ')))
wynik = tab[int((n - 1) / 2)]
print(wynik)


n = int(input())
X = list(map(int, input().split()))
X.sort()
if n % 2 == 1:
	print(X[n // 2])
else:
	print(X[n // 2 - 1])


import math
n = int(input())
a = list(map(int, input().split()))
a.sort()
print(a[math.floor((n - 1) / 2)])


input()
x = sorted(map(int, input().split()))
suml = 0
sumr = sum(x)
res = 0
resv = float('inf')
for i in range(len(x)):
	dist = x[i] * i - suml + sumr - x[i] * (len(x) - i)
	if dist < resv:
		res = x[i]
		resv = dist
	suml += x[i]
	sumr -= x[i]
print(res)


def opPoint(arr, point):
	range = 0
	for t in arr:
		range += abs(point - t)
	return range

def diff(len, ind, val):
	return (2 * ind - len) * val
len = int(input())
a = list(map(int, input().split()))
a.sort()
av = sum(a) / len
min_ind = a[0]
min_range = opPoint(a, a[0])
last_r = min_range
for i in range(1, len):
	last_r = last_r + diff(len, i, a[i] - a[i - 1])
	if min_range > last_r:
		min_range = last_r
		min_ind = a[i]
print(min_ind)