Median

Input

An ordered sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math] such that a comparison [math]\displaystyle{ c }[/math] is defined on the component type [math]\displaystyle{ C }[/math] of [math]\displaystyle{ S }[/math].

Output

1. If [math]\displaystyle{ n }[/math] is odd, the median is the unique value [math]\displaystyle{ x \in \{ S[1],...,S[n]\} }[/math] such that
   1. [math]\displaystyle{ S[i]\lt x }[/math] for at most [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] positions [math]\displaystyle{ i }[/math] of [math]\displaystyle{ S }[/math] and
   2. [math]\displaystyle{ S[i]\gt x }[/math] for at most [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] positions [math]\displaystyle{ i }[/math] of [math]\displaystyle{ S }[/math].
2. On the other hand, if [math]\displaystyle{ n }[/math] is even, the median is [math]\displaystyle{ (x+y)/2 }[/math], where [math]\displaystyle{ x,y \in \{ S[1],...,S[n]\} }[/math] (let [math]\displaystyle{ x \le y }[/math]) are the unique values such that
   1. [math]\displaystyle{ S[i]\lt x }[/math] for at most [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] positions [math]\displaystyle{ i }[/math] of [math]\displaystyle{ S }[/math], and
   2. [math]\displaystyle{ S[i]\gt y }[/math] for at most [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] positions [math]\displaystyle{ i }[/math] of [math]\displaystyle{ S }[/math].

Objective

N/A