import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as VA
main=V.mapM_ print.solve.V.tail.V.unfoldr(B.readInt.B.dropWhile isSpace)=<<B.getContents
solve xs=V.map f xs where
  f x=if x<=a then b else a
  [a,b]=V.toList.V.slice(V.length xs`div`2-1)2.V.modify VA.sort$xs