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

Difficulty: interview

Starter code:

Solutions:
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])

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


#imports
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 #lt, le, eq, ne, ge, gt,  xor  notit, lshift, rshift,      neg, add, mul, sub,
from operator import __not__ as notit
from operator import __abs__ as absit
from operator import __or__ as orit

#PI, E, PHI, INF
PHI, PHI2 = (1 + 5 ** 0.5) / 2, (5 ** 0.5 - 1) / 2
INF = float('inf')

#structures
class TreeNode:
    def __init__(self, v):
        self.val = v
        self.left = None
        self.right = None

#Bit Manipulation
#<<, >>, bin(), int(s, 2)
def setBit(x, offset):
    return x | 1 << offset #RHS: mask
def clearBit(x, offset):
    return x & ~(1 << offset) #RHS: mask
def getBit(x, offset):
    return 1 if testBit(x, offset) > 0 else 0
def testBit(x, offset):
    return x & 1 << offset #RHS: mask
def flipBitAt(x, offset):
    return x ^ 1 << offset #RHS: mask
def flipBits(x, length=-1): #default: x.bit_length() - 1
    length = x.bit_length()-1 if length == -1 else length
    return x ^ (1 << length) - 1
def numBits(x):
    return x.bit_length() #int.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)

#IO
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)]

#Math
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: #is not zero
        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): #for each number
        if x: #found a prime
            primes.append(i)
            mults = i * i
            while mults <= n:
                isp[mults] = False
                mults += i
    return primes
def primeFactor(n): #without a sieve
    factors = Counter()
    while not n&1:
        factors[2] += 1
        n >>= 1
    trynum = 3
    while trynum <= ceil(sqrt(n)): #just in case
        while n % trynum == 0:
            factors[trynum] += 1
            n //= trynum
        trynum += 2
    if n != 1:
        factors[n] += 1
    return factors
def isPrime(n): #num -> boolean
    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

#Iteration
def zipNWith(f, *x): #xs, ys, ... zs -> elementwise f -> os #return map(lambda *y: f(y), x) #list way: [f(y) for y in zip(*xs)]
    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))

















#Input

#Body

#Output
n = getVal(int)
nums = getList(int)
nums.sort()
mid = (n-1) // 2
print(nums[mid])

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

from collections import defaultdict
import sys

def __starting_point():
    #n, m = list(map(int, input().split()))
    n = int(input())
    index = list(map(int, input().split()))
    index.sort()
    print(index[(n - 1) // 2])

__starting_point()

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])


'''
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·105) 
— the number of points on the line.

The second line contains n integers x[i] ( - 109 ≤ x[i] ≤ 109) 
— 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.
'''

import io
import sys
import time
import random
#~ start = time.clock()
#~ test ='''4
#~ 1 2'''

#~ sys.stdin = io.StringIO(test)

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 ] )
         
#~ dur = time.clock()-start
#~ print("Time:",dur)


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

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())
x = sorted(list(map(int,input().split())))
print(x[(n-1)//2])


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):
    #print(l[i] , r[i])
    if mn > l[i] + r[i]:
        mn = l[i] + r[i]
        ind = i
print(a[ind])

n = int(input())
points = list(map(int, input().split()))
points.sort()
print(points[(len(points) - 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])


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
    '''values = [calcVal(points[leftDex], points), calcVal(points[rightDex], points)]
    minVal = min(values)
    which = values.index(minVal)
    if which == 0:
        print(points[leftDex])
    else:
        print(points[rightDex])'''
    print(points[leftDex])
else:
    index = len(points)//2
    print(points[index])
    


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())
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())
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)

n = int(input())

pos = [int(x) for x in input().split()]
pos.sort()

print(pos[(n-1)//2])


n = int(input())
a = [0] + sorted(list(map(int, input().split())))

if n % 2 == 0:
    print(a[n // 2])
else:
    print(a[(n // 2) + 1])

#!/usr/bin/env python3

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


def __starting_point():
    main()

__starting_point()

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]))


n = int(input())

N = sorted(map(int, input().split()))

if n % 2 == 0:
        print(N[(n - 1) //2])
else:
        print(N[n//2 ])


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])

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)])